Repair an off-by-one error

An off-by-one error means a loop runs one pass too many or one pass too few. It is one of the most common faults in algorithm questions, and exam tasks often give you a faulty loop and ask for the repair.

This lesson builds on tracing count-controlled and condition-controlled loops in repetition and arrays. It matters again as soon as arrays appear.

How do you find the faulty line?

Work in this order:

1. State what the loop should do, in numbers. For example, “add the first 10 whole numbers, so 10 passes, answer 55”.
2. Trace the first pass and the last pass.
3. Count the passes the code really makes.
4. Compare. If the code makes one too few or too many, look at the start value, end value and the comparison sign.

Worked example

A programmer wants the total of the whole numbers 1 to 10.

Total ← 0
FOR i ← 1 TO 9
   Total ← Total + i
NEXT i
OUTPUT Total

The loop values are 1 to 9, which is 9 passes. The task needs 10 passes.

The output is 45, but 1 + 2 + … + 10 = 55. The missing value is 10, and 45 + 10 = 55. The repair is to change the end value:

FOR i ← 1 TO 10

A WHILE loop can hide the same fault in its condition. This version should print the first four multiples of 3, which are 3, 6, 9 and 12.

Count ← 0
WHILE Count <= 4 DO
   Count ← Count + 1
   OUTPUT Count * 3
ENDWHILE

The test is true for Count = 0, 1, 2, 3 and 4, so there are 5 passes. It prints 3, 6, 9, 12 and 15. Changing the condition to Count < 4 gives passes for Count = 0, 1, 2 and 3. That prints 3, 6, 9 and 12, which is correct.

The mistake to watch for

A common slip is to repair the output instead of the loop.

Mistaken fix: “The total is 45 and it should be 55, so write OUTPUT Total + 10.”

This gives 55 for this input only. The loop still skips the last value, and any other end value will fail.

The correction is to change the loop bound so that it makes the right number of passes. Then trace a second small case, such as the numbers 1 to 3 (total 6), to confirm.

Check yourself

1. An array Score[1:5] holds five values. The code is FOR i ← 0 TO 4. What is wrong, and what is the repair?

2. How many passes does FOR i ← 5 TO 12 make?

3. This loop should output 2, 4 and 6 only. It outputs 2, 4, 6 and 8. Give the repair.

n ← 0
WHILE n < 8 DO
   n ← n + 2
   OUTPUT n
ENDWHILE

Where this leads next

Next, use a correct loop to scan a list in finding a maximum in a supplied list. The pseudocode trace trainer lets you step a faulty loop and watch the first and last pass.

A teacher in Computer Science tuition can bring you new faulty loops and ask you to explain the repair before you write it.