Putting It Together: Control-Flow Problems

New words in this topic, in plain English. Come back here whenever one feels fuzzy.

Edge case

An unusual input at the limits, such as 0, 1, a negative number or an empty array, where code often breaks.

Divisor

A number that divides another exactly. 3 is a divisor of 12 because 12 % 3 == 0.

Prime number

A whole number greater than 1 whose only divisors are 1 and itself: 2, 3, 5, 7, 11...

GCD

Greatest common divisor: the largest number that divides both of two numbers. The GCD of 48 and 18 is 6.

LCM

Least common multiple: the smallest number both divide into. LCM(a, b) = a / GCD(a, b) × b.

Fibonacci sequence

0, 1, 1, 2, 3, 5, 8...: each number is the sum of the two before it.

Armstrong number

A number equal to the sum of its digits each raised to the power of the digit count, like 153 = 1³ + 5³ + 3³.

Binary

Base 2: numbers written with only 0 and 1. 13 in binary is 1101.

1. 1

   Break FizzBuzz on purpose

   Move the i % 15 == 0 test to the bottom of the ladder. Predict what 15 prints, then run. (Fizz, because 15 % 3 == 0 is checked first.)

2. 2

   Measure the square-root trick

   In 'Primes up to 50', change the inner test to d < n (no square root). Run it and compare the number of divisions with 95. Then set limit to 10000 for both versions and compare again.

3. 3

   Find the overflow point

   In 'GCD, LCM and Fibonacci', change 47 to 46 and run. F(46) = 1,836,311,903 still fits in an int. Then try 47 again with long f1, f2.

Errors are the best teachers. Make each change, read the error, guess what went wrong, then reveal the answer.

public class Main {
    public static void main(String[] args) {
        long fact = 0;
        for (int i = 1; i <= 5; i++) {
            fact *= i;
        }
        System.out.println("5! = " + fact);
    }
}

public class Main {
    public static void main(String[] args) {
        int n = 1;
        boolean prime = true;
        for (int d = 2; d * d <= n; d++) {
            if (n % d == 0) { prime = false; break; }
        }
        System.out.println(n + " prime? " + prime);
    }
}

1. 1

   Plan before typing. Write a few inputs and their expected outputs, including edge cases (0, 1, negative numbers, the biggest value). Describe the steps in plain words. Then choose the loop: for when you know the count, while when you loop until something happens.

2. 2

   Order of checks matters (Topic 2.1). In FizzBuzz, test 'divisible by 15' (or both 3 and 5) before 3 and 5 alone, or 15 prints Fizz.

3. 3

   Stop early when you can (Topic 2.8). To test whether n is prime, you only need to try divisors up to √n, because any factor larger than √n pairs with one smaller than √n. Stop at the first divisor you find. This turns n steps into √n steps: for one million, 1,000 instead of 1,000,000.

4. 4

   Peel off digits with % 10 and / 10 (Topic 2.5) for digit sums, reversal, palindromes and Armstrong numbers. Repeated division with % 2 and / 2 gives binary digits.

5. 5

   Keep a running result in an accumulator: a sum starts at 0, a product at 1, a maximum at the first element (or Integer.MIN_VALUE). Choose the type for the largest possible answer: Fibonacci numbers pass int's limit at the 47th term (Topic 1.3).

6. 6

   Euclid's algorithm for the greatest common divisor, while (b != 0) { int t = a % b; a = b; b = t; }, is over 2,000 years old and still the fastest simple method. It's a perfect example of a loop whose count you don't know in advance.

• ↔

  Trial division needs no memory and is best for testing a few numbers; a sieve costs O(n) memory but answers 'all primes below n' far faster.

• ↔

  Building strings with + in a loop (as in the binary example) is clear but creates a new String each time; for long outputs use StringBuilder (Phase 8).

• ↔

  int is fast and enough for most counters; long delays overflow; BigInteger never overflows but is much slower. Pick the smallest type that is certainly big enough.

• Done when you can write FizzBuzz, an is-prime check with √n and early exit, and Euclid's GCD without looking.

• Done when you can peel digits for sums, reversal, palindromes and binary conversion.

• Done when you choose accumulator start values and types deliberately, including overflow limits.

• Done when you test every solution with edge cases (0, 1, negatives, largest values).

• Done when you can explain the sieve of Eratosthenes and its trade-off against trial division.