AhmedLo - 1 year ago 67

Java Question

I have spent so much time trying to find the formula for this code, but still nothing .. I know the running time but the question really is, what if n = 100 for example, how many line of output will this code print without tracing through ? So, if I found the exact formula, I would answer the question without tracing. This is the code

`int i, j, k;`

for( i = 1; i <= n; i++ )

for ( j = i+1; j <= n; j++ )

for( k = j+1; k <= n; k++ )

{

System.out.println( i + " " + j + " " + k);

}

Answer Source

I have a feeling that you are requiring a **formula** to get number of iteration the nested loops will.

```
for( i = 1; i <= n; i++ )
for ( j = i+1; j <= n; j++ )
for( k = j+1; k <= n; k++ )
```

For those loops, the number of iterations will be:

```
(n*(n-1)*(n-2))/6, where n > 2.
```

**Generic formula** for above kind loops:

```
(n*(n-1)* ... *(n-r+1)) / r!, where n > r-1.
```

Here, r = number of loops

For example: when n = 20 and r = 3, number of iterations will be = (20*19*18) / 3! = 1140