Chapter 2.2: Control Flow

📝 Prerequisites: Chapter 2.1 (variables, cin/cout, basic arithmetic)

2.2.0 What is "Control Flow"?

So far, every program we wrote ran top to bottom — line 1, line 2, line 3, done. Like reading a book straight through.

But real programs need to make decisions and repeat things. That's what "control flow" means — controlling the flow (order) of execution.

Think of it like a "Choose Your Own Adventure" book:

• Sometimes you're told "if you want to fight the dragon, turn to page 47; otherwise turn to page 52"
• Sometimes you're told "repeat this section until you escape the dungeon"

C++ gives us exactly this with:

• if/else — make decisions based on conditions
• for/while loops — repeat a section of code

Here's a visual overview:

In the loop diagram: the program keeps going back to Step 2 until the condition becomes false, then it exits to Step 3.

2.2.1 The if Statement

The if statement lets your program make a decision: "if this condition is true, do this thing."

Basic if

#include <bits/stdc++.h>
using namespace std;

int main() {
    int score;
    cin >> score;

    if (score >= 90) {
        cout << "Excellent!\n";
    }

    cout << "Done.\n";  // always runs regardless of score
    return 0;
}

If score is 95: prints Excellent! then Done. If score is 80: prints only Done. (the if-block is skipped)

if / else

int score;
cin >> score;

if (score >= 60) {
    cout << "Pass\n";
} else {
    cout << "Fail\n";
}

The else block runs only when the if condition is false. Exactly one of the two blocks will run.

if / else if / else Chains

When you have multiple conditions to check:

int score;
cin >> score;

if (score >= 90) {
    cout << "A\n";
} else if (score >= 80) {
    cout << "B\n";
} else if (score >= 70) {
    cout << "C\n";
} else if (score >= 60) {
    cout << "D\n";
} else {
    cout << "F\n";
}

C++ checks these conditions in order, from top to bottom, and runs the first one that's true. Once it runs one block, it skips all the remaining else if/else blocks.

So if score = 85:

1. Is 85 >= 90? No → skip
2. Is 85 >= 80? Yes → print "B", then jump past all the else-ifs

🤔 Why does this work? When we reach else if (score >= 80), we already know score < 90 (because if it were ≥ 90, the first condition would have caught it). Each else if implicitly assumes all the previous conditions were false.

Comparison Operators

Logical Operators (Combining Conditions)

int x, y;
cin >> x >> y;

if (x > 0 && y > 0) {
    cout << "Both positive\n";
}

if (x < 0 || y < 0) {
    cout << "At least one is negative\n";
}

bool done = false;
if (!done) {
    cout << "Still working...\n";
}

🐛 Common Bug: = vs ==

This is one of the most common mistakes for beginners (and even experienced programmers!):

int x = 5;

// DANGEROUS BUG:
if (x = 10) {   // This ASSIGNS 10 to x, doesn't compare!
                 // x becomes 10, and since 10 is nonzero, this is always TRUE
    cout << "x is 10\n";  // This ALWAYS runs, even though x started as 5!
}

// CORRECT:
if (x == 10) {  // This COMPARES x with 10
    cout << "x is 10\n";  // Only runs when x actually equals 10
}

The = operator assigns (stores a value). The == operator compares (checks if two values are equal). They look similar but do completely different things.

⚡ Pro Tip: Some programmers write 10 == x instead of x == 10 — if you accidentally type = instead of ==, it becomes 10 = x which is a compile error (you can't assign to a literal). This is called a "Yoda condition."

Nested if Statements

You can put if statements inside other if statements:

int age, income;
cin >> age >> income;

if (age >= 18) {
    cout << "Adult\n";
    if (income > 50000) {
        cout << "High income adult\n";
    } else {
        cout << "Standard income adult\n";
    }
} else {
    cout << "Minor\n";
}

Be careful: each else matches the nearest preceding if that doesn't already have an else.

2.2.2 The while Loop

A while loop repeats a block of code as long as its condition is true. When the condition becomes false, execution continues after the loop.

while (condition) {
    body (runs over and over)
}

#include <bits/stdc++.h>
using namespace std;

int main() {
    int i = 1;             // 1. Initialize before the loop
    while (i <= 5) {       // 2. Check condition — if false, skip the loop
        cout << i << "\n"; // 3. Run the body
        i++;               // 4. Update — VERY IMPORTANT! Forget this → infinite loop
    }
    // After loop: i = 6, condition 6 <= 5 is false, loop exits
    return 0;
}

Output:

1
2
3
4
5

🐛 Common Bug: Infinite Loop

If you forget to update the variable (step 4 above), the condition never becomes false and the loop runs forever!

int i = 1;
while (i <= 5) {
    cout << i << "\n";
    // BUG: forgot i++ — this prints "1" forever!
}

If your program seems stuck, press Ctrl+C to stop it.

When to use while vs for

• Use while when you don't know in advance how many iterations you need
• Use for when you do know the count (we'll cover for next)

Classic while use case: read until a condition is met.

// Common USACO pattern: read until end of input
int x;
while (cin >> x) {    // cin >> x returns false when input runs out
    cout << x * 2 << "\n";
}

do-while Loop

A do-while loop always runs its body at least once, then checks the condition:

int n;
do {
    cin >> n;
} while (n <= 0);   // keep re-reading until user gives a positive number

This is useful when you want to execute something before checking whether to repeat. It's rare in competitive programming but worth knowing.

2.2.3 The for Loop

The for loop is the most used loop in competitive programming. It packages initialization, condition-check, and update into one clean line:

for (initialization; condition; update) {
    body
}

This is equivalent to:

initialization;
while (condition) {
    body
    update;
}

Visual: For Loop Flowchart

The flowchart above traces the execution: initialization runs once, then the condition is checked before every iteration. When false, the loop exits.

Common for Patterns

// Count from 0 to 9 (standard competitive programming pattern)
for (int i = 0; i < 10; i++) {
    cout << i << " ";
}
// Prints: 0 1 2 3 4 5 6 7 8 9

// Count from 1 to n (inclusive)
int n = 5;
for (int i = 1; i <= n; i++) {
    cout << i << " ";
}
// Prints: 1 2 3 4 5

// Count backwards
for (int i = 10; i >= 1; i--) {
    cout << i << " ";
}
// Prints: 10 9 8 7 6 5 4 3 2 1

// Count by steps of 2
for (int i = 0; i <= 10; i += 2) {
    cout << i << " ";
}
// Prints: 0 2 4 6 8 10

🧠 Loop Tracing: Understanding Exactly What Happens

When learning loops, trace through them manually. Here's how:

Code: for (int i = 0; i < 4; i++) cout << i * i << " ";

Practice tracing loops on paper before running them — it builds intuition and helps spot bugs.

The Most Common USACO Loop Pattern

Read N numbers and process each one:

int n;
cin >> n;

for (int i = 0; i < n; i++) {
    int x;
    cin >> x;
    // process x here
    cout << x * 2 << "\n";
}

⚡ Pro Tip: In competitive programming, for (int i = 0; i < n; i++) with 0-based indexing is standard. It matches how arrays are indexed (Chapter 2.3), so everything lines up neatly.

2.2.4 Nested Loops

You can put a loop inside another loop. The inner loop runs completely for each single iteration of the outer loop.

// Print a 4x4 multiplication table
for (int i = 1; i <= 4; i++) {         // outer: rows
    for (int j = 1; j <= 4; j++) {     // inner: columns
        cout << i * j << "\t";          // \t = tab character
    }
    cout << "\n";  // newline after each row
}

Output:

1   2   3   4
2   4   6   8
3   6   9   12
4   8   12  16

Tracing the first two rows:

i=1: j=1→print 1, j=2→print 2, j=3→print 3, j=4→print 4, then newline
i=2: j=1→print 2, j=2→print 4, j=3→print 6, j=4→print 8, then newline
...

⚠️ Nested Loop Time Complexity

💡 Why should you care about loop counts? In competitions, your program typically needs to finish within 1-2 seconds. A modern computer can execute roughly 10^8 to 10^9 simple operations per second. So if you can estimate how many times your loop body executes in total, you can determine whether it will exceed the time limit (TLE). This is the core idea behind "time complexity analysis" — we'll study it in greater depth in later chapters.

A single loop of N iterations does N operations. Two nested loops of N do N × N = N² operations.

If N = 1000 and you have two nested loops, that's 10^6 operations — fine. But if N = 100,000, that's 10^10 — too slow!

🧠 Quick Rule of Thumb: After seeing the range of N, use the table above to work backwards and determine the maximum number of nested loops you can afford. For example, N ≤ 10^5 → you can only use O(N) or O(N log N) algorithms; N ≤ 5000 → O(N²) is acceptable. This technique is extremely useful in USACO!

2.2.5 Switch Statements

When you have a variable and want to check many specific values, switch is cleaner than a long chain of if/else if:

int day;
cin >> day;

switch (day) {
    case 1:
        cout << "Monday\n";
        break;   // IMPORTANT: break exits the switch
    case 2:
        cout << "Tuesday\n";
        break;
    case 3:
        cout << "Wednesday\n";
        break;
    case 4:
        cout << "Thursday\n";
        break;
    case 5:
        cout << "Friday\n";
        break;
    case 6:
    case 7:
        cout << "Weekend!\n";  // cases 6 and 7 share this code
        break;
    default:
        cout << "Invalid day\n";  // runs if no case matches
}

When to use switch vs if-else

🐛 Common Bug: Forgetting break — Without break, execution "falls through" to the next case!

int x = 2;
switch (x) {
    case 1:
        cout << "one\n";
    case 2:
        cout << "two\n";   // this runs
    case 3:
        cout << "three\n"; // ALSO runs (fall-through!) because no break after case 2
}
// Output: two\nthree\n  (surprising!)

2.2.6 break and continue

break — Exit the Loop Immediately

// Find the first number divisible by 7 between 1 and 100
for (int i = 1; i <= 100; i++) {
    if (i % 7 == 0) {
        cout << "First multiple of 7: " << i << "\n";  // prints 7
        break;  // stop searching — we found it
    }
}

continue — Skip to the Next Iteration

// Print all numbers 1 to 10 except multiples of 3
for (int i = 1; i <= 10; i++) {
    if (i % 3 == 0) {
        continue;  // skip the rest of this iteration, go to i++
    }
    cout << i << " ";
}
// Output: 1 2 4 5 7 8 10

break in Nested Loops

break only exits the innermost loop. To exit multiple levels, use a flag variable:

bool found = false;
int target = 25;

for (int i = 0; i < 10 && !found; i++) {    // outer loop also checks !found
    for (int j = 0; j < 10; j++) {
        if (i * j == target) {
            cout << i << " * " << j << " = " << target << "\n";
            found = true;
            break;   // exits inner loop; outer loop exits too because of !found
        }
    }
}

2.2.7 Classic Loop Patterns in Competitive Programming

These patterns appear in nearly every USACO solution. Learn them cold.

Pattern 1: Read N Numbers, Compute Sum

int n;
cin >> n;

long long sum = 0;
for (int i = 0; i < n; i++) {
    int x;
    cin >> x;
    sum += x;
}
cout << sum << "\n";

Complexity Analysis:

• Time: O(N) — iterate through N numbers, each processed in O(1)
• Space: O(1) — only one accumulator variable sum

Pattern 2: Find Maximum (and Minimum) in a List

int n;
cin >> n;

int maxVal, minVal;
cin >> maxVal;    // read first element
minVal = maxVal;  // initialize both max and min to first element

for (int i = 1; i < n; i++) {   // start from 2nd element (index 1)
    int x;
    cin >> x;
    if (x > maxVal) maxVal = x;
    if (x < minVal) minVal = x;
}

cout << "Max: " << maxVal << "\n";
cout << "Min: " << minVal << "\n";

Complexity Analysis:

• Time: O(N) — iterate through N numbers, each comparison in O(1)
• Space: O(1) — only two variables maxVal and minVal

🤔 Why initialize to the first element? Don't initialize max to 0! What if all numbers are negative? Initializing to the first element guarantees we start with a real value from the input.

Pattern 3: Count How Many Satisfy a Condition

int n;
cin >> n;

int count = 0;
for (int i = 0; i < n; i++) {
    int x;
    cin >> x;
    if (x % 2 == 0) {   // condition: even number
        count++;
    }
}
cout << "Even count: " << count << "\n";

Pattern 4: Print a Star Triangle Pattern

int n;
cin >> n;

for (int row = 1; row <= n; row++) {     // row goes from 1 to n
    for (int col = 1; col <= row; col++) { // print `row` stars per row
        cout << "*";
    }
    cout << "\n";  // newline after each row
}

For n=4, output:

*
**
***
****

Pattern 5: Compute Sum of Digits

int n;
cin >> n;

int digitSum = 0;
while (n > 0) {
    digitSum += n % 10;  // last digit
    n /= 10;             // remove last digit
}
cout << digitSum << "\n";

Tracing for n = 12345:

n=12345: digitSum += 5, n becomes 1234
n=1234:  digitSum += 4, n becomes 123
n=123:   digitSum += 3, n becomes 12
n=12:    digitSum += 2, n becomes 1
n=1:     digitSum += 1, n becomes 0
n=0: loop exits. digitSum = 15 ✓

2.2.8 Complete Example: USACO-Style Problem

Problem: You have N cows. Each cow has a milk production rating. Find the highest-rated cow's rating and count how many cows produce above-average milk.

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    // We need to store all values to compare against the average
    // (We'll learn arrays/vectors in Chapter 2.3 — for now use two passes)

    // First pass: find sum and max
    long long sum = 0;
    int maxMilk = 0;
    vector<int> milk(n);   // store all values (preview of Chapter 2.3)

    for (int i = 0; i < n; i++) {
        cin >> milk[i];
        sum += milk[i];
        if (milk[i] > maxMilk) maxMilk = milk[i];
    }

    double avg = (double)sum / n;

    // Second pass: count above-average
    int aboveAvg = 0;
    for (int i = 0; i < n; i++) {
        if (milk[i] > avg) aboveAvg++;
    }

    cout << "Maximum: " << maxMilk << "\n";
    cout << "Above average: " << aboveAvg << "\n";

    return 0;
}

Sample Input:

5
10 20 30 40 50

Sample Output:

Maximum: 50
Above average: 2

(Average is 30; cows with 40 and 50 are above average → 2 cows)

Complexity Analysis:

• Time: O(N) — two passes (read + count), each O(N), total O(2N) = O(N)
• Space: O(N) — uses vector<int> milk(n) to store all data

⚠️ Common Mistakes in Chapter 2.2

Chapter Summary

📌 Key Takeaways

🧩 Five Classic Loop Patterns Quick Reference

❓ FAQ (Frequently Asked Questions)

Q1: Can for and while replace each other? When should I use which?

A: Yes, any for loop can be rewritten as a while loop, and vice versa. Rule of thumb: if you know the number of iterations (e.g., "loop N times"), use for; if you don't know the count (e.g., "read until end of input"), use while. In competitions, for is used about 90% of the time.

Q2: How many levels deep can nested loops go? Is there a limit?

A: Syntactically there's no limit, but in practice you should be cautious beyond 3 levels. Two nested loops give O(N²), three give O(N³). When N ≥ 1000, three nested loops can easily time out. If you find yourself needing more than 3 levels of nesting, it usually means you need a more efficient algorithm (covered in later chapters).

Q3: break only exits the innermost loop. How do I break out of multiple nested loops at once?

A: Two common approaches: ① Use a bool found = false flag variable, and have the outer loop also check !found; ② Wrap the nested loops in a function and use return to exit directly. Approach ① is more common — see Section 2.2.6 for a complete example.

Q4: Which is faster, switch or if-else if?

A: For a small number of cases (< 10), performance is virtually identical. The advantage of switch is code readability, not speed. In competitions, you can freely choose either. If conditions involve range comparisons (like x > 10), you must use if-else.

Q5: My program produces correct output, but after submission it shows TLE (Time Limit Exceeded). What should I do?

A: Step one: estimate your algorithm's complexity. Look at the range of N → use the "nested loop complexity table" from this chapter to estimate total operations → if it exceeds 10^8, you need to optimize. Common optimization strategies include: reducing the number of loop levels, replacing brute-force search with sorting + binary search (Chapter 3.3), and replacing repeated summation with prefix sums (Chapter 3.2).

🔗 Connections to Later Chapters

• Chapter 2.3 (Functions & Arrays) will let you encapsulate the loop patterns from this chapter into functions, and use arrays to store collections of data
• Chapter 3.2 (Arrays & Prefix Sums) will teach you how to optimize O(N²) range sum queries to O(N) preprocessing + O(1) per query — one of the solutions for when "nested loops are too slow"
• Chapter 3.3 (Sorting & Searching) will teach you binary search, optimizing the O(N) linear search from this chapter to O(log N)
• The five classic loop patterns learned in this chapter (summation, finding max/min, counting, nested iteration, digit processing) are the foundational building blocks for all algorithms in this book
• Nested loop complexity analysis is the first step toward understanding time complexity (a theme throughout the entire book)

Practice Problems

🌡️ Warm-Up Problems

Warm-up 2.2.1 — Count to Ten Print the numbers 1 through 10, each on its own line. Use a for loop.

#include <bits/stdc++.h>
using namespace std;

int main() {
    for (int i = 1; i <= 10; i++) {
        cout << i << "\n";
    }
    return 0;
}

Warm-up 2.2.2 — Even Numbers Print all even numbers from 2 to 20, each on its own line.

#include <bits/stdc++.h>
using namespace std;

int main() {
    // Option 1: step by 2
    for (int i = 2; i <= 20; i += 2) {
        cout << i << "\n";
    }
    return 0;
}

Warm-up 2.2.3 — Sign Check Read one integer. Print Positive if it's > 0, Negative if it's < 0, Zero if it's 0.

Sample Input: -5 → Output: Negative

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;

    if (n > 0) {
        cout << "Positive\n";
    } else if (n < 0) {
        cout << "Negative\n";
    } else {
        cout << "Zero\n";
    }

    return 0;
}

Warm-up 2.2.4 — Multiplication Table of 3 Print the first 10 multiples of 3 (i.e., 3, 6, 9, ..., 30), each on its own line.

#include <bits/stdc++.h>
using namespace std;

int main() {
    for (int i = 1; i <= 10; i++) {
        cout << i * 3 << "\n";
    }
    return 0;
}

Warm-up 2.2.5 — Sum of Five Read exactly 5 integers (on separate lines or the same line). Print their sum.

Sample Input: 3 7 2 8 5 → Output: 25

#include <bits/stdc++.h>
using namespace std;

int main() {
    long long sum = 0;
    for (int i = 0; i < 5; i++) {
        int x;
        cin >> x;
        sum += x;
    }
    cout << sum << "\n";
    return 0;
}

🏋️ Core Practice Problems

Problem 2.2.6 — FizzBuzz The classic programming challenge: print numbers from 1 to 100. But:

• If the number is divisible by 3, print Fizz instead
• If divisible by 5, print Buzz instead
• If divisible by both 3 and 5, print FizzBuzz instead

First few lines of output:

1
2
Fizz
4
Buzz
Fizz
7
8
Fizz
Buzz
11
Fizz
13
14
FizzBuzz

#include <bits/stdc++.h>
using namespace std;

int main() {
    for (int i = 1; i <= 100; i++) {
        if (i % 3 == 0 && i % 5 == 0) {
            cout << "FizzBuzz\n";
        } else if (i % 3 == 0) {
            cout << "Fizz\n";
        } else if (i % 5 == 0) {
            cout << "Buzz\n";
        } else {
            cout << i << "\n";
        }
    }
    return 0;
}

Problem 2.2.7 — Minimum of N Read N (1 ≤ N ≤ 1000), then read N integers. Print the minimum value.

Sample Input:

5
8 3 7 1 9

Sample Output: 1

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    int first;
    cin >> first;
    int minVal = first;  // initialize to first element

    for (int i = 1; i < n; i++) {   // read remaining n-1 elements
        int x;
        cin >> x;
        if (x < minVal) {
            minVal = x;
        }
    }

    cout << minVal << "\n";
    return 0;
}

Problem 2.2.8 — Count Positives Read N (1 ≤ N ≤ 1000), then read N integers. Print how many of them are strictly positive (> 0).

Sample Input:

6
3 -1 0 5 -2 7

Sample Output: 3

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    int count = 0;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        if (x > 0) {
            count++;
        }
    }

    cout << count << "\n";
    return 0;
}

Problem 2.2.9 — Star Triangle Read N. Print a right triangle of * characters with N rows, where row i has i stars.

Sample Input: 4

Sample Output:

*
**
***
****

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;

    for (int row = 1; row <= n; row++) {
        for (int star = 1; star <= row; star++) {
            cout << "*";
        }
        cout << "\n";
    }

    return 0;
}

Problem 2.2.10 — Sum of Digits Read a positive integer N (1 ≤ N ≤ 10^9). Print the sum of its digits.

Sample Input: 12345 → Sample Output: 15 Sample Input: 9999 → Sample Output: 36

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;

    int digitSum = 0;
    while (n > 0) {
        digitSum += n % 10;  // add last digit
        n /= 10;             // remove last digit
    }

    cout << digitSum << "\n";
    return 0;
}

🏆 Challenge Problems

Challenge 2.2.11 — Collatz Sequence The Collatz sequence starting from N works as follows:

• If N is even: next = N / 2
• If N is odd: next = N * 3 + 1
• Stop when N = 1

Read N. Print the entire sequence (including N and 1). Also print how many steps it takes to reach 1.

Sample Input: 6 Sample Output:

6 3 10 5 16 8 4 2 1
Steps: 8

#include <bits/stdc++.h>
using namespace std;

int main() {
    long long n;
    cin >> n;

    int steps = 0;
    cout << n;         // print starting number

    while (n != 1) {
        if (n % 2 == 0) {
            n = n / 2;
        } else {
            n = n * 3 + 1;
        }
        cout << " " << n;  // print each next number
        steps++;
    }
    cout << "\n";
    cout << "Steps: " << steps << "\n";

    return 0;
}

Challenge 2.2.12 — Prime Check Read N (2 ≤ N ≤ 10^6). Print prime if N is prime, composite otherwise.

A number is prime if it has no divisors other than 1 and itself.

Sample Input: 17 → Output: prime Sample Input: 100 → Output: composite

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;

    bool isPrime = true;

    if (n < 2) {
        isPrime = false;
    } else {
        // Check divisors from 2 to sqrt(n)
        for (int i = 2; (long long)i * i <= n; i++) {
            if (n % i == 0) {
                isPrime = false;
                break;  // found a divisor, no need to continue
            }
        }
    }

    cout << (isPrime ? "prime" : "composite") << "\n";
    return 0;
}

Challenge 2.2.13 — Highest Rated Cow Read N (1 ≤ N ≤ 1000), then read N pairs of (cow name, rating). Find and print the name of the cow with the highest rating.

Sample Input:

4
Bessie 95
Elsie 82
Moo 95
Daisy 88

Sample Output: Bessie (If there's a tie, print the name of the first one that appeared.)

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    string bestName;
    int bestRating = -1;  // initialize to -1 so any real rating beats it

    for (int i = 0; i < n; i++) {
        string name;
        int rating;
        cin >> name >> rating;

        if (rating > bestRating) {
            bestRating = rating;
            bestName = name;
        }
    }

    cout << bestName << "\n";
    return 0;
}