May 14, 2010
Number of Iterations
Problem
If you run the following block of java code. How many times the print statement is going to execute.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
public class Counting { public static void main(String[] args) { for (int i = 0; i < 100; i++) { for (int j = 100; j > i; j--) { System.out.println("Looping"); } } } } |
Solution
You can modify the code by adding a counter then let the code itself calculates how many times it
executes however that is not what the problem is all about. You can trace the code but this is a
time consuming process. In order to find an exact number regardless of the loop limits you need
to use a counting technique. Consider the two nested loops as a nested sum as follows:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
Sum [i = 0 .. 99 ] (Sum [ j = 100 .. i + 1 ] (1)) Sum [i = 1 .. 100] (Sum [ j = i + 1 .. 100 ] (1)) Sum [i = 1 .. 100] (100 - (i + 1) + 1) Sum [i = 1 .. 100] (100 - i) let k = 100 - i the last sum becomes: Sum [k = 99 .. 0 ] (k) which is the same as: Sum [k = 1 .. 100] (k) = 100(100+1)/2 = 5050 because Sum [i = 1 .. N] (i) = N(N+1)/2 |
About Author
Mohammed Abualrob
Software Engineer @ Cisco