1

What is the approach to solve "nested for" loops?

Ex -

for(i=0;i<10;i++)
for(j=i;j<10;j++)
for(k=j;k<10;k++)
for(l=k;l<10;l++)
for(m=l;m<10;m++)
   count++;

gives count = 2002..?? (14C5)

I thought of 10 * (10 + 9) * (10 + 9 + 8) ........ *(10+9+8+7+6) which is giving way wrong. Also, I thought of 15C5. But it is also incorrect.

The answer is coming as.. For first loop, it is 10/1
For second loop, it is 10*11/(2*1)
For third loop, its is 10*11*12 / (3*2*1) and so on..

Kindly correct me and provide me with the correct approach to solve such questions as the interviewers always modify such questions..

2 Answers 2

1

Here's a counting argument for why the closed form is:

(10 + (number of loops - 1)) choose (number of loops)

Consider the case when the number of loops is three so we have three iterators. Now visualize the values of the iterators during the execution of the algorithm. It's hard to put into words rigorously, but hopefully this helps:

0 | | | 1 2 3 4 5 6 7 8 9
0 | | 1 | 2 3 4 5 6 7 8 9
0 | | 1 2 | 3 4 5 6 7 8 9
...
0 | 1 | | 2 3 4 5 6 7 8 9
0 | 1 | 2 | 3 4 5 6 7 8 9
0 | 1 | 2 3 | 4 5 6 7 8 9
...
0 1 | | | 2 3 4 5 6 7 8 9
0 1 | | 2 | 3 4 5 6 7 8 9
...
0 1 2 3 4 5 6 7 8 9 | | |

It is literally the same as having 12 slots (the leftmost slot is always 0) where we choose three slots for the iterators and then fill the rest sequentially with [1-9]. For example, one possible choice is {0, 5, 7} in that case you put one iterator in each of those slots and then the numbers 1-9 sequentially:

Slots: 0 1 2 3 4 5 6 7 8 9 10 11
     0 | 1 2 3 4 | 5 6 | 7 8  9

Not my greatest counting argument, but I think it gets the idea across.

Now your actual question was how to come up with this on the spot. Finding the closed form in a short period of time seems pretty difficult. Perhaps they just wanted you to manually figure out that count == 2002 using any small arithmetic shortcuts you saw on the way? The most obvious way to make the manual calculation fast is to take advantage of the recursive nature of the code. You can iteratively calculate count for one loop, two loops, three loops, and so on and use the partial sums to do the next step. By that I mean:

1 Loop:
    10
    Sum: 10
2 Loop:
    10 9 8 7 6 5 4 3 2 1
    Partial Sums: 1
    => 1 + 2 = 3
    => 1 + 2 + 3 = 6
    => 1 + 2 + 3 + 4 = 10
    ...
    => Sum: 55 
3 Loop:
    10 9 8 7 6 5 4 3 2 1
    9 8 7 6 5 4 3 2 1
    8 7 6 5 4 3 2 1
    7 6 5 4 3 2 1
    6 5 4 3 2 1
    5 4 3 2 1
    4 3 2 1
    3 2 1
    2 1
    1
    Partial Sums: 1
    => 1 + 3 = 4
    => 1 + 3 + 6 = 10
    => 1 + 3 + 6 + 10 = 20
    ...

So notice that in the three loop case we can use the partial sums from the two loop case to calculate the sum faster (there's always ten partial sums). I can imagine writing that out in ~15 min, although it'd be pretty painful. Perhaps someone else will chime in with a clever insight...

1
  • thanks for this vivid description. So, I guess, it's better to take the general case for n = 1,2,3 & derive the formula there itself. Aug 11, 2013 at 10:50
0

When posed with programming logic that is beyond what you can properly trace in your head, use a compiler.

The following is a bare minimum C program based on your code snippet that runs through all the for loops and prints the values of all the variables during each iteration.

/* testloop.c */

#include <stdio.h>

int main()
{
        static int count, i, j, k, l, m;

        for(i=0;i<10;i++)
            for(j=i;j<10;j++)
                for(k=j;k<10;k++)
                    for(l=k;l<10;l++)
                        for(m=l;m<10;m++) {
                            printf("i= %d\tj= %d\tk= %d\tl= %d\tm= %d\tcount= %d\n", i, j, k, l, m, count);
                            count++;
                        }   

        printf("After all loops count = %d\n", count);

}

Compile it as follows

$ gcc testloop.c -o testloop

and run it as

$ ./testloop

and observe the output to understand the flow of code.

0   0   0   0   0   count = 0
0   0   0   0   1   count = 1
0   0   0   0   2   count = 2
0   0   0   0   3   count = 3
0   0   0   0   4   count = 4
...
... (1985 more lines)
...
7   7   9   9   9   count = 1990
7   8   8   8   8   count = 1991
7   8   8   8   9   count = 1992
7   8   8   9   9   count = 1993
7   8   9   9   9   count = 1994
7   9   9   9   9   count = 1995
8   8   8   8   8   count = 1996
8   8   8   8   9   count = 1997
8   8   8   9   9   count = 1998
8   8   9   9   9   count = 1999
8   9   9   9   9   count = 2000
9   9   9   9   9   count = 2001
After all loops count = 2002
2
  • Of course sir, but taking compiler alongwith is not allowed in any written examination..!! Aug 11, 2013 at 11:03
  • ..and thats why you need to practise beforehand. Good Luck. Aug 11, 2013 at 11:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.