Classic loop problems

Why this matters

Interviewers rarely ask you to write a loop from nothing. They ask a problem that a loop solves, and they watch how you reason. Can you name the state the loop must keep? Can you tell whether the answer will fit in the number type you chose? Do you know how much work the loop does as the input grows? The problems in this lesson come up again and again. Each one is a small pattern, and each pattern appears inside larger programs, so knowing them well saves time in both exams and projects.

Solve each problem with a clear plan, say its time and space cost out loud, and check the edge cases. Those three habits matter more than the exact code.

Start from the first principle: a loop keeps a small state

Every loop in this lesson keeps a little state, meaning the values it remembers from one pass to the next. A digit loop remembers the number that is left to process and the digits it has seen. A Fibonacci loop remembers the last two terms. A binary search remembers the low end, the high end and the middle. If you can name the state, you can usually write the loop, because the state tells you the starting values, the test and the update.

Programmers often describe the state with a sentence that must stay true before and after every pass. This sentence is called an invariant. For example, in a running sum, the invariant is: "after pass k, the sum holds the total of the first k values." If you can state the invariant, you can check that each pass keeps it true. You can also use it to convince an interviewer that the loop is correct before you run anything.

An everyday analogy: a recipe card

Think of each problem in this lesson as a recipe card. The card lists the ingredients, which are the variables you need. It lists the steps, which are the loop body. And it says when to stop, which is the test. A cook who knows a few basic recipes can cook many dishes, because the same techniques repeat. In the same way, a few loop patterns cover most of the problems you will be asked about.

When you meet a new problem, look for the pattern it resembles. Is it about each digit of a number? That is the digit pattern. Does it combine two running values? That is the Fibonacci pattern. Does it search a sorted list? That is binary search. Matching the problem to a pattern is most of the work.

Pattern 1: peel off digits

To work with the digits of a number, take the last digit with % 10 and remove it with / 10. The number 4729 gives the digits 9, then 2, then 7, then 4. Each step is one pass of the loop. The loop stops when the number reaches 0.

The picture below shows the same steps for 4729. Read it from top to bottom. The number on the left shrinks by one digit each time, and the digit on the right is the one that was removed.

Digit peeling of 4729: each row divides the number by ten and shows the digit removed, 9, then 2, then 7, then 4, until the number is zero

Three quantities can be built in the same loop: the number of digits, the sum of the digits and the reversed number. The reversal works because each pass shifts the reversed number one place to the left, then adds the new digit in the empty place. Here is the complete program. Type 4729 into the Input box.

The output for 4729 is:

Digits: 4
Digit sum: 22
Reversed: 9274

Trace rev one pass at a time. It starts at 0. After the first digit, 9, it is 9. After the second digit, 2, it is 9 times 10 plus 2, which is 92. After the third digit, 7, it is 927. After the fourth, 4, it is 9274. Each pass multiplies the old value by ten and adds the new digit, so the digits end up in reverse order.

This loop uses do-while on purpose. The number 0 has one digit, and a while loop with the test temp > 0 would count it as zero digits. The do-while runs the body once before the test, so 0 gives Digits: 1, which is correct. Try the input 0 to confirm.

The time is O(d), where d is the number of digits, which is about log base 10 of the number. The space is O(1), because only a fixed number of variables is used. Interviewers often ask for both numbers, so state them.

A palindrome is a number that reads the same reversed, such as 1221. To test it, compare the reversed value with the original. The original must be kept in a separate variable, because the loop destroys its input. The debugging walkthrough later in this lesson shows what happens when it is not.

Pattern 2: factorial and the overflow trap

The factorial of n, written n!, is the product of the whole numbers from 1 to n. Five factorial is 1 times 2 times 3 times 4 times 5, which is 120. The loop starts the product at 1, not 0, because 0 multiplied by anything is 0. The loop multiplies by each number in turn.

Type 20 into the Input box. The output is:

20! = 2432902008176640000

Factorials grow very fast. The value 13! is already larger than the largest 32-bit int, which is about 2.1 billion. A program that uses int for the product gets the wrong answer, and C++ does not stop it. Signed overflow is undefined behaviour, which means the compiler may do anything, so the printed number can be meaningless or even negative. The compiler does not warn you by default.

The 64-bit long long holds values up to about 9.2 quintillion, and 20! is the largest factorial that fits in it. For 21 and above, the answer overflows a long long too. If an interviewer asks for 25!, the right answer is to explain that the result needs a big-integer library or a different representation, not to print a wrong number.

The time is O(n), because the loop runs once per factor, and the space is O(1). The multiplication itself takes time proportional to the size of the number, which interviewers usually ignore at this level, but it is worth mentioning when the numbers become very large.

Pattern 3: Fibonacci with two running values

Fibonacci numbers start with 0 and 1, and each later term is the sum of the two before it. The sequence is 0, 1, 1, 2, 3, 5, 8, and so on. A loop needs only the last two terms, so it keeps two variables and moves them forward. This is the key to the pattern: keep the state small.

Type 10 into the Input box. The output is:

0 1 1 2 3 5 8 13 21 34 
sum 88

Trace the state. Before the first pass, a is 0 and b is 1. The first pass prints 0, then computes next as 1, then moves a to 1 and b to 1. The second pass prints 1, computes 2, and moves on. After each pass, a holds the current term, and b holds the next one. The three lines inside the body are the heart of the pattern: compute the next term, shift the window, and keep the sum.

The loop does one step per term, so the time is O(n). The space is O(1). A famous mistake is to compute Fibonacci numbers by calling the function recursively for each term. That approach does the same work over and over, and its time grows exponentially. The recursion module covers why, and the loop above is the fix.

The values grow fast too. Fibonacci number 92 is the largest that fits in a long long. Ask the same question as with factorials: what is the largest n the type can hold?

Pattern 4: primes with a sieve

In the previous lesson you tested one number for primality. To list all primes up to a limit, a faster method is the sieve of Eratosthenes. The idea is to start with every number from 2 to the limit marked as possibly prime. Then, for each prime you find, mark all of its multiples as not prime. The numbers still unmarked at the end are the primes.

The program below uses a bool array as the marks. The value true means "crossed out". The outer loop walks the numbers in order. When it finds an unmarked number, that number is prime, and the inner loop crosses out its multiples, starting at its square, because smaller multiples were crossed out by smaller primes.

Type 100 into the Input box. The program accepts a limit up to 1000, because the array has fixed size.

The output for 100 is:

primes up to 100: 25, largest 97

The inner loop starts at i * i because every smaller multiple of i has a smaller prime factor and was already crossed out. For i equal to 5, the first multiple to cross out is 25, since 5 and 10 were crossed out by 2. This saves work, and it is the detail interviewers check for.

The time is O(n log log n), which is close to linear for practical limits. The space is O(n) for the array. Compare this with testing each number separately, which takes about n times the square root of n steps. The sieve is the better choice when you need all the primes up to a limit, and the single test is the better choice when you need one prime.

Pattern 5: greatest common divisor by Euclid's method

The greatest common divisor of two numbers is the largest number that divides both. Euclid's method finds it with a loop that repeats the same step. Replace the pair (a, b) with (b, a % b). Stop when b is 0. The value left in a is the answer.

The reason this works is that the remainder keeps the common divisors the same. If a number divides both a and b, it also divides a % b, so no common divisor is lost by replacing a with b and b with the remainder. The pairs get smaller on each step, so the loop must end.

Type 48 18 into the Input box.

The output is:

gcd 6, lcm 144

Trace the pair step by step:

The answer is x at the end, which is 6. The least common multiple is a / g * b, which is 48 divided by 6, times 18, equal to 144. The division comes first, so the product stays smaller and is less likely to overflow.

The time is O(log of the smaller number), because the remainders shrink quickly. Every two steps of the loop at least halve the larger of the two numbers. Take the pair (1000, 999): the remainder is 1, and the next pair is (999, 1), which finishes in one more step. Take the pair (1000, 1): the remainder is 0 at once. The worst case is a pair of consecutive Fibonacci numbers, where each step only cuts the numbers down by a fixed ratio, which is still logarithmic. The space is O(1). Check the edge cases: gcd(0, 5) is 5, and gcd(5, 0) is 5 with no loop passes. gcd(0, 0) is undefined in mathematics, and the loop returns 0 for it, so say so if the question allows zeros.

Pattern 6: counting pairs in a sorted array

In the nested loops lesson, you counted pairs of values that add up to a target with two nested loops. That takes O(n squared) time. When the array is sorted, a much faster method uses two pointers: one at the start, one at the end. The sum of the two pointed values tells you which pointer to move. If the sum is too small, the left pointer moves right, because only a larger value can increase the sum. If the sum is too big, the right pointer moves left.

The picture below shows two pointers moving toward each other on a sorted array. Study it, then use the visualizer to watch the same moves happen.

The counting version has one extra detail. Values can repeat, and each pair of positions counts, even when the values are equal. When the sum matches, the program counts the run of equal values at each pointer and multiplies the two counts. When both pointers point to equal values, every pair inside the remaining range matches, and the count is a number of pairs taken two at a time.

Type the three lines 6, then -3 -1 0 2 4 4, then 3 into the Input box, one on each line.

The output is:

2

The two pairs are (-3, 4) and (-1, 4). The array has two 4s, so each pairs with the -3 and the -1 in turn, but the counting branch multiplies the run lengths. Trace the first moves: the sum of -3 and 4 is 1, which is less than 3, so l moves to -1. The sum of -1 and 4 is 3, which matches. The left run of -1 has one value, the right run of 4s has two, and the product 1 times 2 gives 2 pairs. Both pointers then move past their runs and the loop ends.

The time is O(n), because each pointer moves at most n steps. The space is O(1) beyond the array. The sorted order is the precondition. On an unsorted array, the pointer moves are meaningless, and the program gives wrong answers without any error message. Always say that the input must be sorted, and ask the interviewer whether you can sort it first. Sorting costs O(n log n), which is still better than O(n squared) for a large input.

Pattern 7: binary search for the first position at or above a value

Binary search, which you met in the first lesson, has a version that interviewers ask about more than the exact match. Instead of finding a value, it finds the first position where the value is at least x. This is called the lower bound. It is useful for ranking, scheduling and for finding where a new value would be inserted in a sorted list.

The loop keeps a range [lo, hi) that always contains the answer. The value hi is one past the last position still in play, so a range with lo equal to hi is empty and holds the answer. At each step, the program looks at the middle. If the middle value is at least x, the answer is at the middle or to its left, so hi moves to the middle. Otherwise the answer is to the right, and lo moves past the middle.

Type 5, then 1 3 3 7 10, then 4 into the Input box, on separate lines.

The output is:

first position at or above 4 is 3

Step through the same search below, and watch the shaded range shrink from both sides.

Trace the search. The range starts as [0, 5). The middle is index 2, which holds 3. That is less than 4, so lo becomes 3. The range is now [3, 5), with middle 4, which holds 10. That is at least 4, so hi becomes 4. The range is [3, 4), with middle 3, which holds 7. That is at least 4, so hi becomes 3. Now lo equals hi, so the loop stops, and the answer is 3.

Notice what happens when every value is smaller than x. The loop keeps moving lo right until it reaches n, which means "no position". Programs must handle that case. The same is true when x is smaller than every value, where the answer is 0.

The time is O(log n), because the range halves each pass. The space is O(1). The loop uses the lo + (hi - lo) / 2 form for the middle, which avoids an overflow that the simpler (lo + hi) / 2 can cause when the positions are very large. Interviewers notice this detail.

How to explain a loop answer in an interview

Writing the code is only half of an interview answer. The other half is explaining it, and interviewers often judge a candidate by the explanation. A reliable way to explain a loop answer has four parts, and you can say them in about a minute.

Start with the idea. Say what the loop keeps track of, in one sentence. For example, "the loop keeps the last two Fibonacci terms and moves them forward." Then say why this works, which is the invariant. For example, "after each pass, the first variable holds the current term, and the second holds the next one."

Next, walk through a small example aloud. Choose an input with two or three values, and trace the variables pass by pass. This shows the interviewer that you can run the code in your head, and it often reveals an edge-case bug before the interviewer finds it.

Then state the cost. Give the time first, then the extra space, and explain each in terms of the passes. For a single loop over n values, say that the loop makes n passes, each doing a fixed amount of work, so the time is O(n). For the extra space, name the variables you keep, and say that they do not grow with the input.

Finally, name the edge cases you checked. Zero, one, empty input, negative numbers and the largest value the type can hold are the usual ones. Saying that you checked them shows judgement, even if the interviewer does not ask about them.

A common trap is to write the code first and explain it afterwards, without a plan. Try to state the idea before you type. If you cannot, the interviewer will see that as a sign that you do not yet know the solution, even if your code happens to work.

Summary table of costs

Interviewers often ask for the time and space of each algorithm. The table below lists the problems in this lesson. Learn the entries until you can give them without looking.

The "d" is the number of digits, and "log n" means the number of times you can halve n before it reaches 1. Be ready to explain why each complexity is what it is, using the loop's passes as the reason.

Common mistakes and what they look like

An overflowing product. Factorial, a large sum of squares or a product of two large values can overflow an int, and no compiler message appears. The symptom is a result that is too small, too large or negative. The fix is a wider type, such as long long, and a check of the largest input the problem allows.

A factorial or product started at 0. Every product then stays 0. Start products at 1 and sums at 0.

A destroyed input. The digit loops change the number they work on. If you need the original later, copy it first. The palindrome bug in the debugging walkthrough below is exactly this mistake.

A sieve with the wrong array size. The array must have room for the largest index. The sieve here uses size 1001 for limits up to 1000. Writing composite[j] with j beyond the array reads or writes memory it does not own, and C++ does not check. The program may appear to work, then fail on a different input.

Two pointers on unsorted data. The pointers only make sense when the array is sorted. Sort the array first, or use a different method, and say so in your answer.

A lower bound that returns n by mistake. If the search runs off the end, the answer is n, not n - 1. Make sure the caller knows that n means "not found".

An integer middle that overflows. The form (lo + hi) / 2 can overflow when both values are close to the largest int. Use lo + (hi - lo) / 2 instead.

Debugging walkthrough: the palindrome check that always fails

Here is a palindrome check. It should print palindrome for 1221, but it prints not palindrome:

#include <iostream>
using namespace std;
 
int main() {
    int n = 1221;
    int rev = 0;
    while (n > 0) {
        rev = rev * 10 + n % 10;
        n = n / 10;
    }
    if (rev == n) {
        cout << "palindrome" << endl;
    } else {
        cout << "not palindrome" << endl;
    }
    return 0;
}

The output is:

not palindrome

Do not guess. Trace the variables. The reversal loop builds rev correctly, and for 1221 it reaches 1221. But the same loop also drives n down to 0, because n = n / 10 runs on every pass. After the loop, n is 0. The comparison rev == n is therefore 1221 == 0, which is false.

The fix is to keep the original number in a second variable, and compare with that. Here is the corrected program:

#include <iostream>
using namespace std;
 
int main() {
    int n = 1221;
    int original = n;
    int rev = 0;
    while (n > 0) {
        rev = rev * 10 + n % 10;
        n = n / 10;
    }
    if (rev == original) {
        cout << "palindrome" << endl;
    } else {
        cout << "not palindrome" << endl;
    }
    return 0;
}

This version prints palindrome. The lesson is general. When a loop changes a variable, and you need its original value afterwards, store a copy before the loop. Ask the question every time you use a value after a loop that changed it.

Variations and edge cases

Negative numbers. The digit loops above assume the input is zero or positive. For a negative number, n % 10 is negative in C++, which breaks the loop. Take the absolute value first, or handle the sign separately, as the reversal exercise in the module assignment asks you to do.

Zero. Zero has one digit, a factorial of 0 is 1, the first Fibonacci term is 0, and the sieve for limit 0 finds no primes. Test zero every time a problem allows it, because it breaks many loops that start with a test.

Size of the answer. Before you pick a number type, ask how large the answer can be. Use long long for products and sums that can get big, and state the largest input your solution handles.

Empty input. An empty array has no pairs, no first position at or above a value and no largest value. Decide what the program prints in that case, and test it.

Equal values. In the pair counter, equal values form runs, and the runs need their own counts. In binary search, equal values make the first position matter. Test an input where every value is the same.

Interview questions this lesson prepares you for

Reverse a number and check if it is a palindrome. The answer is the digit loop with a copy of the original. O(d) time and O(1) space.

Compute the nth Fibonacci number. Use two running values, O(n) time and O(1) space. Mention that the naive recursion takes exponential time, and why.

Find all primes up to n. Use the sieve, O(n log log n) time and O(n) space. Mention that starting each inner loop at i * i avoids repeated work.

Count pairs in a sorted array with a given sum. Use two pointers, O(n) time and O(1) extra space. State that the input must be sorted, and that a sort costs O(n log n) if it is not.

Find the first position where a value could be inserted in a sorted list. Use the lower bound, O(log n) time. Explain why the search halves the range each pass.

Real-world uses

Digit loops power checksums, such as the one that checks a credit card number. Factorial and product loops count arrangements in scheduling and statistics. Fibonacci-style loops appear in simulations of growth and in some compression code. The sieve is used in cryptography tests and in generating test data. GCD appears in fractions, in time calculations that mix cycles, and in graphics that reduce ratios. Two pointers and binary search are the basis of many database and search features, where a sorted index answers a question in a few steps instead of a full scan.

Practice

Write each program, predict the output and check it. Hidden solutions are under each exercise.

1. Read a number and print palindrome or not palindrome. Use a copy of the original number. Test with 1221, 1234 and 7. Hint: keep the original in a second variable before the loop.

#include <iostream>
using namespace std;
 
int main() {
    int n;
    cin >> n;
    int original = n;
    int rev = 0;
    while (n > 0) {
        rev = rev * 10 + n % 10;
        n = n / 10;
    }
    if (rev == original) {
        cout << "palindrome" << endl;
    } else {
        cout << "not palindrome" << endl;
    }
    return 0;
}

2. Print the sum of the first 10 Fibonacci numbers. The answer is 88. Hint: add a inside the loop, before the two values move forward.

#include <iostream>
using namespace std;
 
int main() {
    long long a = 0, b = 1;
    long long sum = 0;
    for (int i = 0; i < 10; i++) {
        sum += a;
        long long next = a + b;
        a = b;
        b = next;
    }
    cout << sum << endl;
    return 0;
}

3. Read a number n and print its factorial as a long long. For 20 the answer is 2432902008176640000. Hint: start the product at 1.

4. Find the least common multiple of three numbers, read from input, using the GCD. For 4 6 10 the answer is 60. Hint: the LCM of two numbers is a / gcd(a, b) * b, and you can apply it twice.

#include <iostream>
using namespace std;
 
long long gcdOf(long long a, long long b) {
    while (b != 0) {
        long long r = a % b;
        a = b;
        b = r;
    }
    return a;
}
 
int main() {
    long long x, y, z;
    cin >> x >> y >> z;
    long long l = x / gcdOf(x, y) * y;
    l = l / gcdOf(l, z) * z;
    cout << l << endl;
    return 0;
}

5. Print the number of digits of a number entered as a long long, using a loop that is correct for 0. For the input 0 the answer is 1, and for 9075 it is 4. Hint: a do-while loop counts at least one digit.

#include <iostream>
using namespace std;
 
int main() {
    long long n;
    cin >> n;
    int digits = 0;
    long long t = n;
    do {
        t /= 10;
        digits++;
    } while (t > 0);
    cout << digits << endl;
    return 0;
}

6. Count the primes up to 1000 with the sieve from pattern 4. The answer is 168. Hint: the array must hold 1001 values, indexes 0 to 1000.

7. Given a sorted array and a target, print yes if any two different positions have values that add up to the target, and no otherwise. Use two pointers. For the array 1 3 5 8 and target 9, the answer is yes, because 1 + 8 = 9. Hint: stop as soon as you find a match.

#include <iostream>
#include <vector>
using namespace std;
 
int main() {
    int n;
    cin >> n;
    vector<long long> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    long long target;
    cin >> target;
 
    bool found = false;
    int l = 0, r = n - 1;
    while (l < r && !found) {
        long long s = a[l] + a[r];
        if (s == target) {
            found = true;
        } else if (s < target) {
            l++;
        } else {
            r--;
        }
    }
    cout << (found ? "yes" : "no") << endl;
    return 0;
}

8. For the array 5 5 5 2 2 9, print the length of the longest run of equal values that sit next to each other. For this array the answer is 3. Hint: keep a current run length that grows while the value repeats and resets when the value changes.

#include <iostream>
using namespace std;
 
int main() {
    int a[6] = {5, 5, 5, 2, 2, 9};
    int n = 6;
    int best = 1, run = 1;
    for (int i = 1; i < n; i++) {
        if (a[i] == a[i - 1]) {
            run++;
        } else {
            run = 1;
        }
        if (run > best) {
            best = run;
        }
    }
    cout << best << endl;
    return 0;
}

9. Explain why the lo + (hi - lo) / 2 form is safer than (lo + hi) / 2 in binary search, and find a pair of values that breaks the second form. Hint: think about values close to the largest int.

10. A while (n > 0) loop counts the digits of the input 0 as 0, but the correct count is 1. Explain why the while version fails for 0, and say what the digit sum of 0 should be. Hint: the test is checked before the body runs.

What you now know

• Name the state a loop must keep, and state its invariant, before you write the code.
• Digit loops divide by 10 and use % 10 to read the last digit. A do-while handles the input 0 correctly.
• A factorial or Fibonacci loop keeps a small running value. Check the largest input the number type can hold.
• The sieve crosses out multiples in an inner loop that starts at i * i, in O(n log log n) time.
• Euclid's method replaces the pair with its remainder until one value is 0, and the LCM is a / gcd * b.
• Two pointers on a sorted array count pairs in O(n) time. Binary search for the lower bound takes O(log n) time.
• Keep a copy of any value you need after a loop changes it.