AP Computer Science A

Counting loops summary

A lot of College Board problems depend on being able to tell how many times a loop runs. Below I’ve cataloged a number of kinds of loops in order of increasing complexity with information about how to figure out how many times a loop will run using a bit of simple math. Note that if you skip to the section on “Step loops” and master the formula for the most general form it handles the first two kinds of loops as well.

Remember that counting loops can also be written as while loops. For those while loops you can use the formulas in this document as long as you identify the initializer (usually a variable declaration right before the while), the condition (that’s easy, it’s in the while), and the updater (usually the last line of the body). However not all while loops are simple counting loops. (For that matter, not all for loops are either so the first thing you may need to check when looking at any loop is whether it’s a counting loop in the sense of having a loop variable that starts at a number and goes to another number in uniform steps.)

Simple counting loops

These loops loop up or down from or to 0 or sometimes 1. They are the most common loops, used to iterate over the elements of a String, array, or ArrayList. You should be able to look at loops like these, especially the three upward loops, and tell almost instantly how many times the loop body will run.

for (int i = 0; i < num; i++) {}
          

for (int i = 1; i <= num; i++) {}
          

for (int i = num; i > 0; i--) {}
          

for (int i = 0; i <= num; i++) {}
          

for (int i = num; i >= 0; i--) {}
          

Range loops

These loops are similar to simple counting loops but they start at some arbitrary number other than 0 or 1. They are useful for iterating over a substring of a String or a subsection of an array or ArrayList. You have to do a bit of subtraction to figure out how many times the loop body will run.

for (int i = start; i < end; i++) {}
          

for (int i = start; i <= end; i++) {}
          

for (int i = start; i > end; i--) {}
          

for (int i = start; i >= end; i--) {}
          

Step loops

The final generalization of counting loops, step loops are like range loops with the added wrinkle that the loop variable is incremented or decremented by some number other than 1. If start. and end are multiples of step these can be converted to a simple or range loop and then in the body of the loop instead of using the loop variable use the loop variable times step. This can often make the code easier to read because it’s easier to understand how many times the loop will run just by looking at the loop header.

If start and end are not multiples of step you need to think more carefully about when the loop will end. But in either case the formulas below will let you figure out with one subtraction, and one rounding division how many times the loop body will run.

for (int i = start; i < end; i += step) {}
          

for (int i = start; i > end; i -= step) {}
          

for (int i = start; i <= end; i += step) {}
          

for (int i = start; i >= end; i -= step) {}
          

Note that when the comparator is < or > the number of iterations is the larger index minus the smaller index divided by the step size and when it’s <= or >= we subtract the smaller from the larger and then add one before dividing by step size. And in either case, we round up after dividing. This formula works for all the other kinds of loops which are just more specific cases of these step loop forms with step being 1 and—in the case of simple loops—one of start or end being 0 or 1 which makes the subtraction pretty easy.

Nested loops

When we talk about how many times a nested loop runs we usually mean the body of the innermost loop. The only trick to analyzing such loops, is to correctly analyze both the outer and inner loops and then multiply the number of times each loop runs. For instance:

for (int i = 0; i < 10; i++) {
  for (int j = 0; j < 12; j++) {
    System.out.print("*");
  }
}
  

It’s easy to see that the outer loop runs 10 times and the inner loop runs 12 times. Thus the call to System.out.print will happen 10 x 12 or 120 times.

Obviously if the loops are more complex it won’t be as easy to read off the number of times but we can still analyze each loop independently. Consider, for instance, this mess:

int i = 38;
while (i >= -17) {
  for (int j = -13; j < 15; j += 3) {
    System.out.print("*");
  }
  i -= 5;
}
  

We can analyze the outer loop as a step loop from 38 down to -17 by 5 with a >= in the condition. So ((38 - -17) + 1) / 5 or 56/5 which gives us a bit more than 11 so 12 iterations. And the inner loop is from -13 up to 15 by 3’s with a < in the condition so (15 - -13) / 3 or 28 / 3 which is 9 and a bit so rounding up gives us 10. Now 12 times 10 gives us 120 for the number of times the inner body of these nested loops will be run.

Array/ArrayList/String loop recipes

Below are some common patterns for traversing 1D and 2D arrays. These also work with ArrayLists, if you replace a.length with list.size()and a[i] with list.get(i). And the one-dimensional recipes work with Strings, if you replace a.length with s.length() and a[i] with s.substring(i, i + 1).

for (int i = 0; i < a.length; i++) {
  // do something with a[i]
}
          

for (int i = a.length - 1; i >= 0; i--) {
// do something with a[i]
}
          

for (int row = 0; row < a.length; row++) {
  for (int col = 0; col < a[0].length; col++) {
    // do something with a[row][col]
  }
}
          

for (int row = a.length - 1; row >= 0; row++) {
  for (int col = 0; col < a[0].length; col++) {
    // do something with a[row][col]
  }
}
          

for (int col = 0; col < a[0].length; row++) {
  for (int row = 0; row < a.length; row++) {
    // do something with a[row][col]
  }
}
          

for (int i = 0; i < a.length; i++) {
  for (int j = 0; j < a.length; j++) {
    // do something with a[i] and a[j]
  }
}
          

for (int i = 0; i < a.length; i++) {
  for (int j = i + 1; j < a.length; j++) {
    // do something with a[i] and a[j]
  }
}
          

String-specific loop recipes

for (int i = 0; i < s.length(); i++) {
  for (int j = i + 1; j <= s.length(); j++) {
    // do something with s.substring(i, j)
  }
}
          

for (int i = 0; i <= s.length(); i++) {
  // do something with s.substring(0, i)
}
          

for (int i = 0; i <= s.length(); i++) {
  // do something with s.substring(i)
}