Unit 2: Selection and Iteration

1. The three building blocks

An algorithm is a step-by-step process that solves a problem or completes a task. Every algorithm, from a recipe to a video game, is built from three building blocks: sequencing, selection and repetition 2.1.A.1.

Building block	What it does	Everyday example	Java tool (later in Unit 2)
Sequencing	Runs steps one after another, in order	Put on socks, then shoes	Statements in order
Selection	Makes a decision, then picks which steps run	If it is raining, take an umbrella	if, if-else
Repetition	Repeats steps until a goal is reached	Keep stirring until the sugar dissolves	while, for

Algorithms get selection through decision making and repetition through looping 2.1.A.2. Here is an everyday algorithm, written in plain language, that uses all three:

1. Take the cap off the bottle. (sequencing)
2. If the bottle is dirty, rinse it. (selection)
3. Hold the bottle under the fountain until it is full. (repetition)
4. Put the cap back on. (sequencing)

2. Selection: a true or false decision

Selection happens when the way an algorithm continues depends on a true or false decision 2.1.A.3. The question must have exactly two possible answers. “Is the temperature above 25 degrees?” works. “What is the temperature?” does not, because its answer is a number, not true or false.

Decision	If true	If false
Is the temperature above 25?	Wear shorts	Wear jeans

The same decision in Java (you will learn the if statement in Topic 2.3):

int temperature = 31;
if (temperature > 25) {
    System.out.println("Wear shorts");
} else {
    System.out.println("Wear jeans");
}

Output:

Wear shorts

Watch out: only one of the two paths runs. The program never prints both lines.

3. Repetition: repeat until the desired outcome

In repetition, the same process runs again and again, and it stops once the result you want has been reached 2.1.A.4. In plain language: “Water the plant one cup at a time until the soil moisture reaches 50.”

int moisture = 20;
int cups = 0;
while (moisture < 50) {
    moisture += 15;
    cups++;
}
System.out.println("Cups of water: " + cups);

Output:

Cups of water: 2

Trace it. Each row is one check of the decision “is moisture still below 50?”

Check	moisture < 50?	moisture after the step	cups
1	20 < 50 is true	35	1
2	35 < 50 is true	50	2
3	50 < 50 is false	(stop)	2

Watch out: the repeated step must move toward the desired outcome. If the plant never got any water, the moisture would stay at 20 and the process would never end.

4. Order changes the outcome

Where you place each step of sequencing, selection and repetition helps decide what the algorithm produces, so changing the order can change the result 2.1.A.5. Look at two versions of a game rule. A player has 90 points, earns 15 bonus points, and levels up at 100 points.

Version A checks first, then adds the bonus:

int points = 90;
if (points >= 100) {
    System.out.println("Level up!");
}
points += 15;
System.out.println("Points: " + points);

Output:

Points: 105

Version B adds the bonus first, then checks:

int points = 90;
points += 15;
if (points >= 100) {
    System.out.println("Level up!");
}
System.out.println("Points: " + points);

Output:

Level up!
Points: 105

Same steps, same final points, different behavior. In Version A the decision saw the old value (90), so the player never leveled up.

5. From written steps to code

Writing the algorithm in plain language first helps you choose the right building blocks. Problem: a student saves 12 dollars each week for headphones that cost 50 dollars. How many weeks does it take, and how much extra money is left?

1. Set saved to 0 and weeks to 0.
2. Repeat until saved is at least 50: add 12 to saved and add 1 to weeks.
3. Print the number of weeks.
4. If saved is more than 50, print the extra money.

Each numbered step becomes code:

int saved = 0;
int weeks = 0;
while (saved < 50) {
    saved += 12;
    weeks++;
}
System.out.println("Weeks: " + weeks);
if (saved > 50) {
    System.out.println("Extra: " + (saved - 50));
}

Output:

Weeks: 5
Extra: 10

Notice the translation: “repeat until saved is at least 50” becomes “keep looping while saved is less than 50”. The loop continues while the opposite of the goal is true.

1. Relational operators produce true or false

A relational operator compares two values. An expression that uses one evaluates to a Boolean value, true or false 2.2.A.3. You can print that value or store it in a boolean variable.

Operator	Meaning	Example	Value
==	equal to	4 == 4	true
!=	not equal to	4 != 4	false
<	less than	3 < 8	true
>	greater than	3 > 8	false
<=	less than or equal to	5 <= 5	true
>=	greater than or equal to	2 >= 7	false

int age = 16;
boolean canDrive = age >= 16;
boolean canVote = age >= 18;
System.out.println(canDrive);
System.out.println(canVote);
System.out.println(age != 16);

Output:

true
false
false

Watch out: =<, => and <> are not Java operators. The equals sign always comes second.

2. Comparing numbers with <, >, <= and >=

The operators <, >, <= and >= compare numeric values to find their relationship 2.2.A.2. They work with int and double values, and you can mix the two types: Java widens the int to a double before comparing.

The arithmetic on each side happens first, with the normal Java rules. That makes integer division a classic trap:

int goals = 7;
int games = 2;
System.out.println(goals / games > 3);
System.out.println(goals / games >= 3);
System.out.println((double) goals / games > 3);

Output:

false
true
true

goals / games is 7 / 2, which is 3 in integer division, and 3 > 3 is false. Casting one operand to double gives 3.5, and 3.5 > 3 is true.

Watch out: a range such as “between 0 and 10” cannot be written as 0 < x < 10 in Java. The first comparison gives a boolean, and a boolean cannot be compared with a number.

int x = 5;
boolean inRange = 0 < x < 10;

error: bad operand types for binary operator '<'

You will join two comparisons with && in Topic 2.5.

3. == and != with primitive values

The operators == and != check whether two values are the same 2.2.A.1. With primitive types (int, double, boolean), they compare the actual primitive values.

int lives = 3;
int startLives = 3;
boolean gameOver = false;
System.out.println(lives == startLives);
System.out.println(lives != 0);
System.out.println(gameOver == false);

Output:

true
true
true

Watch out (= versus ==): one equals sign is assignment, two are comparison. Using = where Java expects a Boolean expression is a compile error for int values:

int lives = 3;
if (lives = 0) {
    System.out.println("Game over");
}

error: incompatible types: int cannot be converted to boolean

Watch out (double values): round-off error can make two values that should be equal compare as different.

double total = 0.1 + 0.2;
System.out.println(total == 0.3);
System.out.println(total);

Output:

false
0.30000000000000004

4. == and != with reference types

With reference types, == and != compare the object references, not the contents of the objects 2.2.A.1. A reference tells Java where an object is. Two references are == only when they refer to the same object.

String a = new String("goal");
String b = new String("goal");
String c = a;
System.out.println(a == b);
System.out.println(a == c);
System.out.println(a.equals(b));

Output:

false
true
true

• a == b is false: new created two separate objects, even though both hold the letters “goal”.
• a == c is true: c holds a copy of the reference in a, so both refer to the same object.
• a.equals(b) is true: equals compares the characters.

Watch out: this is the most common String trap on the AP® exam. To ask “do these strings have the same characters?”, use equals, never ==. Topic 2.6 goes deeper into comparing object references.

5. Store the result and reuse it

Because a relational expression evaluates to a Boolean value, you can store the result in a boolean variable with a clear name. This makes later code easier to read.

double temperature = 38.4;
boolean hasFever = temperature >= 38.0;
System.out.println("Fever: " + hasFever);

Output:

Fever: true

Read hasFever = temperature >= 38.0 from right to left: first the comparison gives true, then = stores true in hasFever.

1. Selection changes the flow of control

Normally Java runs statements in sequence, top to bottom. Selection statements change that sequential execution 2.3.A.1. An if statement is a type of selection statement: it affects the flow of control by running different segments of code depending on the value of a Boolean expression 2.3.A.2.

boolean isRaining = true;
if (isRaining) {
    // body: runs only when the Boolean expression is true
}
// the program continues here in every case

The condition must be a Boolean expression inside parentheses. It can be a relational expression (score >= 70) or a boolean variable (isMember).

2. One-way selection: if

Use a one-way selection (if statement) when some code should run in one situation and be skipped otherwise. If the Boolean expression is true, the body runs; if it is false, the body is skipped 2.3.A.3.

int battery = 15;
System.out.println("Checking battery...");
if (battery < 20) {
    System.out.println("Low battery: plug in your phone");
}
System.out.println("Battery: " + battery + "%");

Output:

Checking battery...
Low battery: plug in your phone
Battery: 15%

Trace with two different starting values:

battery	battery < 20	Lines printed
15	true	Checking, Low battery, Battery: 15%
80	false	Checking, Battery: 80%

The last println is after the if, so it runs in both cases.

3. Two-way selection: if-else

Use a two-way selection (if-else statement) when the program has two different segments of code to choose from: one for a true Boolean expression and one for a false one. The if body runs when the expression is true, and the else body runs when it is false 2.3.A.4. Exactly one of the two bodies runs.

int score = 64;
if (score >= 70) {
    System.out.println("Passed");
} else {
    System.out.println("Try again");
}
System.out.println("Done");

Output:

Try again
Done

Inside a method, each branch can return a value. Every path through the method must reach a return.

public static String parity(int n) {
    if (n % 2 == 0) {
        return "even";
    } else {
        return "odd";
    }
}

System.out.println(parity(14));
System.out.println(parity(-3));

Output:

even
odd

4. Two ifs are not an if-else

Two separate if statements are checked one after the other, so both bodies can run. Compare this with the if-else in Section 3.

int temp = 30;
if (temp > 25) {
    System.out.println("Hot");
}
if (temp > 10) {
    System.out.println("Warm");
}

Output:

Hot
Warm

Separate ifs can also change a value that the next if then checks:

int coins = 8;
if (coins < 10) {
    coins += 5;
}
if (coins >= 10) {
    System.out.println("Bonus unlocked");
}
System.out.println(coins);

Output:

Bonus unlocked
13

5. Braces and the stray semicolon

Java ignores indentation. Without braces, an if controls only the very next statement.

int speed = 40;
if (speed > 50)
    System.out.println("Slow down");
    System.out.println("Speeding ticket");

Output:

Speeding ticket

The second println looks like it is inside the if, but it is not, so it runs even though speed > 50 is false.

A semicolon right after the condition is worse: it gives the if an empty body, and the block below always runs.

int speed = 40;
if (speed > 50); {
    System.out.println("Slow down");
}

Output:

Slow down

Watch out: an else with no matching if (for example, after a stray semicolon) does not compile:

int speed = 40;
if (speed > 50); {
    System.out.println("Slow down");
} else {
    System.out.println("OK");
}

error: 'else' without 'if'

Rule for the exam and for your own code: put braces around every if and else body, and never put a semicolon after if (...).

1. An if inside an if

Nested if statements are if, if-else or if-else-if statements written inside the body of another if, if-else or if-else-if statement 2.4.A.1. Use nesting when a second decision only makes sense after the first one.

A cinema charges by age, but only members get the student price:

int age = 15;
boolean isMember = true;
if (age < 18) {
    if (isMember) {
        System.out.println("Ticket: 5 dollars");
    } else {
        System.out.println("Ticket: 8 dollars");
    }
} else {
    System.out.println("Ticket: 12 dollars");
}

Output:

Ticket: 5 dollars

2. The inner condition waits for the outer one

The Boolean expression of the inner if is evaluated only if the outer Boolean expression is true 2.4.A.2. Trace the cinema code with four inputs:

age	isMember	age < 18	isMember checked?	Output
15	true	true	yes, true	Ticket: 5 dollars
15	false	true	yes, false	Ticket: 8 dollars
30	true	false	no	Ticket: 12 dollars
30	false	false	no	Ticket: 12 dollars

When the outer test is false, Java jumps straight to the outer else. The value of isMember does not matter.

3. Multiway selection: if-else-if

A multiway selection (if-else-if) is used when there is a series of expressions, each with its own segment of code. Java checks the expressions from top to bottom, runs no more than one segment (the one for the first expression that evaluates to true) and skips the rest. If no expression is true and there is a trailing else, the else body runs 2.4.A.3.

int score = 84;
String grade;
if (score >= 90) {
    grade = "A";
} else if (score >= 80) {
    grade = "B";
} else if (score >= 70) {
    grade = "C";
} else {
    grade = "F";
}
System.out.println("Grade: " + grade);

Output:

Grade: B

score >= 70 is also true for 84, but it is never checked, because score >= 80 was true first.

score	First true expression	grade
95	score >= 90	A
84	score >= 80	B
70	score >= 70	C
42	none, trailing else	F

4. Order matters in a chain

Because the first true expression wins, the order of the conditions changes the result. This version checks the widest condition first:

int score = 95;
String grade;
if (score >= 70) {
    grade = "C";
} else if (score >= 80) {
    grade = "B";
} else if (score >= 90) {
    grade = "A";
} else {
    grade = "F";
}
System.out.println("Grade: " + grade);

Output:

Grade: C

A score of 95 gets a C, because score >= 70 is true first. The B and A branches can never run. Rule: with >=, put the largest boundary first; with <=, put the smallest boundary first.

Without a trailing else, a chain may run nothing at all:

int windSpeed = 12;
if (windSpeed > 60) {
    System.out.println("Storm warning");
} else if (windSpeed > 30) {
    System.out.println("Strong wind");
}
System.out.println("Report finished");

Output:

Report finished

5. The dangling else

When there are no braces, an else pairs with the nearest earlier if that does not already have an else, no matter how the code is indented. This is called the dangling else.

int x = 5;
int y = 1;
if (x > 3)
    if (y > 3)
        System.out.println("Both big");
else
    System.out.println("x is small");

Output:

x is small

The else is indented under if (x > 3), but it belongs to if (y > 3). Since x > 3 is true and y > 3 is false, the inner else runs and prints a message that is wrong. With braces, the meaning matches the indentation:

int x = 5;
int y = 1;
if (x > 3) {
    if (y > 3) {
        System.out.println("Both big");
    }
} else {
    System.out.println("x is small");
}
System.out.println("End");

Output:

End

1. The three logical operators

Logical operators are used with Boolean expressions 2.5.A.1. Each one produces a Boolean value.

• !a (not) is true if a is false, and false otherwise.
• a && b (and) is true if both a and b are true, and false otherwise.
• a || b (or) is true if a is true, b is true, or both are true, and false otherwise.

A truth table lists every combination of inputs:

a	b	!a	a && b	a || b
true	true	false	true	true
true	false	false	false	true
false	true	true	false	true
false	false	true	false	false

int age = 15;
boolean hasTicket = true;
System.out.println(age >= 13 && hasTicket);
System.out.println(age >= 18 || hasTicket);
System.out.println(!hasTicket);

Output:

true
true
false

An expression that uses logical operators evaluates to a Boolean value, so you can store it, print it or use it as an if condition 2.5.A.1.

2. Order of precedence

When an expression mixes logical operators, Java evaluates ! (not) first, then && (and), then || (or) 2.5.A.1. Arithmetic and relational operators are evaluated before && and ||.

boolean a = true;
boolean b = false;
boolean c = false;
System.out.println(a || b && c);
System.out.println((a || b) && c);
System.out.println(!a || c);

Output:

true
false
false

Step by step for a || b && c: first b && c is false && false, which is false. Then a || false is true || false, which is true. Parentheses change the order: (a || b) && c is true && false, which is false.

Watch out: ! binds very tightly. To negate a comparison, put the comparison in parentheses.

int x = 5;
boolean result = !x > 3;

error: bad operand type int for unary operator '!'

The fix is !(x > 3).

3. Ranges with && and ||

To check whether a value is inside a range, join two comparisons with &&. To check whether it is outside, use ||.

int hour = 22;
boolean openHours = hour >= 9 && hour <= 17;
boolean quietHours = hour < 7 || hour > 21;
System.out.println("Open: " + openHours);
System.out.println("Quiet: " + quietHours);

Output:

Open: false
Quiet: true

Watch out: hour < 7 && hour > 21 can never be true, because no number is both below 7 and above 21. This is a logic error: the code compiles, but the condition is always false.

4. Short-circuit evaluation

Short-circuit evaluation: when the first Boolean expression alone already settles the result of && or ||, Java does not evaluate the second Boolean expression at all 2.5.A.2.

• false && anything is always false, so Java skips anything.
• true || anything is always true, so Java skips anything.

Programmers use this on purpose as a safety check. Here the division only happens when it is safe:

int games = 0;
int points = 40;
if (games != 0 && points / games > 10) {
    System.out.println("High scorer");
} else {
    System.out.println("Not enough data");
}

Output:

Not enough data

games != 0 is false, so points / games is never evaluated. Swap the two sides and the division runs first:

int games = 0;
int points = 40;
if (points / games > 10 && games != 0) {
    System.out.println("High scorer");
}

Output:

Exception in thread "main" java.lang.ArithmeticException: / by zero

The same idea protects a method call on a reference that might be null:

String nickname = null;
if (nickname != null && nickname.length() > 3) {
    System.out.println("Long nickname");
} else {
    System.out.println("No long nickname");
}

Output:

No long nickname

5. Short-circuit and side effects

If the second expression calls a method that does something visible, such as printing, short-circuit evaluation means that call may not happen. Exam questions use this to test whether you really know which side runs.

public class ShortCircuitDemo {
    public static boolean isLong(String word) {
        System.out.println("Checking " + word);
        return word.length() > 5;
    }

    public static void main(String[] args) {
        boolean first = 5 > 2 || isLong("banana");
        System.out.println("first: " + first);
        boolean second = 5 < 2 || isLong("kiwi");
        System.out.println("second: " + second);
    }
}

Output:

first: true
Checking kiwi
second: false

In first, the left side is true, so isLong("banana") is never called and nothing extra is printed. In second, the left side is false, so Java must evaluate the right side: isLong("kiwi") runs, prints its line and returns false.

1. Equivalent expressions and truth tables

Two Boolean expressions are equivalent if they evaluate to the same value in all cases. A truth table can prove they are equivalent 2.6.A.1: list every combination of true and false for the variables, evaluate both expressions in each row, and compare. With two variables there are 4 rows; with three variables there are 8.

Are !(a && b) and !a || !b equivalent?

a	b	a && b	!(a && b)	!a	!b	!a || !b
true	true	true	false	false	false	false
true	false	false	true	false	true	true
false	true	false	true	true	false	true
false	false	false	true	true	true	true

The columns for !(a && b) and !a || !b match in every row, so the expressions are equivalent.

Are !(a && b) and !a && !b equivalent? Row 2 (a true, b false) gives true for the first and false for the second. One row that differs is enough to show two expressions are not equivalent.

boolean a = true;
boolean b = false;
System.out.println(!(a && b));
System.out.println(!a || !b);
System.out.println(!a && !b);

Output:

true
true
false

2. De Morgan’s laws

De Morgan’s laws can be applied to Boolean expressions to create equivalent Boolean expressions 2.6.A.2:

• !(a && b) is equivalent to !a || !b
• !(a || b) is equivalent to !a && !b

To apply a law: move the ! onto each part, and switch && to || (or || to &&). When the parts are comparisons, negate each comparison:

Comparison	Its negation
x > 5	x <= 5
x < 5	x >= 5
x >= 5	x < 5
x == 5	x != 5

Example: !(temp > 30 || isRaining) becomes temp <= 30 && !isRaining. In words: “not (hot or raining)” means “not hot and not raining”.

int temp = 24;
boolean isRaining = false;
boolean original = !(temp > 30 || isRaining);
boolean rewritten = temp <= 30 && !isRaining;
System.out.println(original + " " + rewritten);

Output:

true true

Watch out: a common wrong answer keeps the > and writes temp < 30. For temp equal to 30, !(temp > 30) is true but temp < 30 is false.

3. Two variables, one object

Two different variables can hold references to the same object. Object references can be compared using == and != 2.6.B.1. The comparison is true only when both references point to the same object; it does not look at what is inside the objects.

String teamA = new String("Lions");
String teamB = new String("Lions");
String favorite = teamA;
System.out.println(teamA == favorite);
System.out.println(teamA == teamB);
System.out.println(teamA != teamB);

Output:

true
false
true

Variable	Refers to
teamA	object 1 (“Lions”)
favorite	object 1 (same object as teamA)
teamB	object 2 (“Lions”, a separate object)

Variables like teamA and favorite, which refer to the same object, are called aliases.

Watch out: two string literals with the same characters, such as "Lions" and "Lions", may share one object, so == can happen to be true. Never rely on this: compare string contents with equals.

4. Comparing a reference with null

A reference variable can hold null, which means it does not refer to any object. Comparing a reference with null, using == or !=, tells you whether it actually refers to an object 2.6.B.2.

String winner = null;
if (winner == null) {
    System.out.println("No winner yet");
}
winner = "Tigers";
if (winner != null) {
    System.out.println("Winner: " + winner + " (" + winner.length() + " letters)");
}

Output:

No winner yet
Winner: Tigers (6 letters)

Calling a method such as length() on a null reference throws a NullPointerException. Check for null first, and put that check on the left of && so short-circuit evaluation protects the call: winner != null && winner.length() > 2.

5. equals: equivalency by attributes

Classes often define their own equals method to specify what makes two objects of that class equivalent. The decision is most often based on attributes of the two objects 2.6.B.3.

The String class is the example you use most. Its equals method treats two strings as equivalent when they have the same sequence of characters, even if they are separate objects.

String typed = new String("open sesame");
String password = "open sesame";
System.out.println(typed == password);
System.out.println(typed.equals(password));
System.out.println(typed.equals("Open sesame"));

Output:

false
true
false

Uppercase and lowercase letters are different characters, so the last comparison is false.

Other classes choose their own criteria. A class for library cards might call two cards equal when their card numbers match; a class for points on a grid might compare both coordinates. When an exam question gives you a class with an equals method, read its description to see which attributes it compares. (Writing your own replacement for the equals method is outside the AP® course and exam.)

Question you are asking	Use
Do these two variables refer to the same object?	==
Does this variable refer to any object?	== null or != null
Are these two objects equivalent (same attribute values)?	equals

1. When you need iteration

Iteration is one kind of repetition. An iteration statement changes the flow of control: it sends the program back to run the same segment of code again, for as long as the Boolean expression that controls the loop stays true. That can mean many times, once, or zero times 2.7.A.1. You need iteration when a task repeats the same steps many times, or when you do not know how many times the steps must repeat until the program is running: “add interest until the savings reach 1000”, “keep halving until the value is 1”.

Without a loop you would copy the same lines again and again, and you could not handle a number of repetitions that changes.

2. How a while loop runs

A while loop is a type of iterative statement. The Boolean expression is evaluated before each iteration of the loop body, including the first. When it is true, the body runs. This continues until the expression is false, and then the iteration ends 2.7.B.1.

int countdown = 3;
while (countdown > 0) {
    System.out.println(countdown);
    countdown--;
}
System.out.println("Liftoff!");

Output:

3
2
1
Liftoff!

Check	countdown	countdown > 0	Printed
1	3	true	3
2	2	true	2
3	1	true	1
4	0	false	(loop ends)

The Boolean expression was evaluated 4 times; the body ran 3 times. The variable that controls the loop (countdown) is called the loop control variable. A working loop has three parts: it is initialized before the loop, tested in the condition and updated in the body.

Watch out: the condition is only checked at the top. In the example below, steps passes 10 in the middle of the body, but the rest of the body still runs.

int steps = 8;
while (steps < 10) {
    steps += 3;
    System.out.println("steps = " + steps);
}

Output:

steps = 11

3. Zero iterations

If the Boolean expression is false the first time it is evaluated, the loop body does not run at all 2.7.A.3.

int lives = 0;
while (lives > 0) {
    System.out.println("Playing...");
    lives--;
}
System.out.println("Game over");

Output:

Game over

This matters when a loop depends on its starting values (initial conditions). Ask: “What must be true before the loop starts for it to work as intended?”

4. Infinite loops

If the Boolean expression of a loop is true every time it is checked, the loop never stops: this is an infinite loop 2.7.A.2. The code compiles, but the program never moves past the loop. Three common causes:

Forgetting the update:

int count = 1;
while (count <= 5) {
    System.out.println(count);
}

Updating in the wrong direction:

int count = 1;
while (count <= 5) {
    System.out.println(count);
    count--;
}

count moves away from 5 (1, 0, -1, -2…), so count <= 5 stays true. (Strictly, count would overflow after about two billion iterations, but for the AP® exam this loop is an infinite loop.)

Skipping over the stopping value with !=:

int n = 0;
while (n != 10) {
    n += 4;
}

n goes 0, 4, 8, 12, 16… and is never exactly 10. Writing n < 10 would stop the loop.

A stray semicolon also causes trouble: while (count <= 5); is a loop with an empty body, so count never changes.

5. Off by one errors

An off by one error happens when the loop runs one time too many or one time too few 2.7.A.4. Goal: print the lap numbers 1 to 5.

int lap = 1;
while (lap < 5) {
    System.out.print(lap + " ");
    lap++;
}

Output:

1 2 3 4 

One time too few: when lap is 5, lap < 5 is false. The fix is lap <= 5:

int lap = 1;
while (lap <= 5) {
    System.out.print(lap + " ");
    lap++;
}

Output:

1 2 3 4 5 

Starting at 0 with lap <= 5 would be one time too many (6 iterations). To check any loop, trace the first iteration and the last iteration.

6. Repeat until a goal is reached

while loops are a natural fit when you do not know the number of iterations in advance. A savings account earns 10 percent each year (integer dollars, rounded down). How many years until 100 dollars grows to at least 150?

int balance = 100;
int years = 0;
while (balance < 150) {
    balance = balance + balance / 10;
    years++;
}
System.out.println(years + " years, balance " + balance);

Output:

5 years, balance 160

years at check	balance	balance < 150
0	100	true
1	110	true
2	121	true
3	133	true
4	146	true
5	160	false

Notice balance / 10 is integer division: 121 / 10 is 12 and 133 / 10 is 13.

You can also end a loop early with a condition in the body. Here a boolean variable stops the search at the first multiple of 7 above 50:

int n = 51;
boolean found = false;
while (!found) {
    if (n % 7 == 0) {
        found = true;
    } else {
        n++;
    }
}
System.out.println("First multiple of 7 above 50: " + n);

Output:

First multiple of 7 above 50: 56

Watch out: if the n++ came before the if, the search would skip testing 51. The order of statements in the body decides whether an early exit happens too early, too late or not at all.

1. The three parts of the header

A for loop is a type of iterative statement. Its header has three parts, separated by semicolons: the initialization, the Boolean expression and the update 2.8.A.1.

for (int lap = 1; lap <= 4; lap++) {
    System.out.println("Lap " + lap);
}

Output:

Lap 1
Lap 2
Lap 3
Lap 4

Part	In the example	Job
Initialization	int lap = 1	Create and set the loop control variable
Boolean expression	lap <= 4	Decide whether to run the body again
Update	lap++	Change the loop control variable after each iteration

2. The exact order of execution

The initialization statement runs only once, before the Boolean expression is evaluated for the first time. The variable it initializes is called the loop control variable. The Boolean expression is evaluated right after the initialization and then after each update, until it is false. In each iteration, the update runs after the entire loop body and before the Boolean expression is evaluated again 2.8.A.2.

for (int i = 0; i < 3; i++) {
    System.out.println("body sees i = " + i);
}

Output:

body sees i = 0
body sees i = 1
body sees i = 2

Step	Action	i	Result
1	initialization	0
2	check i < 3	0	true
3	body	0	prints 0
4	update i++	1
5	check i < 3	1	true
6	body	1	prints 1
7	update i++	2
8	check i < 3	2	true
9	body	2	prints 2
10	update i++	3
11	check i < 3	3	false, loop ends

Count from the table: the initialization ran 1 time, the Boolean expression 4 times, the body 3 times and the update 3 times.

A loop control variable declared in the header exists only inside the loop:

for (int i = 0; i < 3; i++) {
    System.out.println(i);
}
System.out.println(i);

error: cannot find symbol

3. Counting iterations and other updates

You can count iterations without tracing every step:

Header	Values of the loop control variable	Iterations
for (int i = 0; i < 10; i++)	0 to 9	10
for (int i = 1; i <= 10; i++)	1 to 10	10
for (int i = 1; i < 10; i++)	1 to 9	9
for (int i = 0; i <= 10; i += 2)	0, 2, 4, 6, 8, 10	6
for (int i = 10; i > 0; i--)	10 down to 1	10
for (int i = 1; i < 100; i *= 3)	1, 3, 9, 27, 81	5

The update does not have to be i++. This loop counts down by 5:

for (int seconds = 20; seconds >= 0; seconds -= 5) {
    System.out.print(seconds + " ");
}

Output:

20 15 10 5 0 

A for loop is a good fit for an accumulator, such as the sum of the even numbers from 2 to 10:

int sum = 0;
for (int n = 2; n <= 10; n += 2) {
    sum += n;
}
System.out.println("Sum: " + sum);

Output:

Sum: 30

4. for and while are interchangeable

A for loop can be rewritten as an equivalent while loop, and the other way around 2.8.A.3. Move the initialization above the loop, keep the Boolean expression, and make the update the last statement of the body.

for (int day = 1; day <= 3; day++) {
    System.out.println("Day " + day);
}

int day = 1;
while (day <= 3) {
    System.out.println("Day " + day);
    day++;
}

Both print the same three lines:

Output:

Day 1
Day 2
Day 3

One difference: in the while version, day is declared before the loop, so it still exists after the loop, with the value 4.

Going the other way, a while loop that halves a value becomes a for loop:

int steps = 0;
for (int size = 64; size > 1; size /= 2) {
    steps++;
}
System.out.println(steps);

Output:

6

5. Common for loop errors

A semicolon after the header gives the loop an empty body. The empty body runs 5 times, then the block runs once:

int total = 0;
for (int i = 0; i < 5; i++); {
    total++;
}
System.out.println(total);

Output:

1

Changing the loop control variable in the body as well as in the header skips values:

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

Output:

0 2 4 6 8 

Each iteration adds 2 to i: once in the body and once in the update. Keep all changes to the loop control variable in the header.

1. Evenly divisible: use the remainder

There are standard algorithms to identify if an integer is or is not evenly divisible by another integer 2.9.A.1. The test is the remainder operator: a % b == 0 means a is evenly divisible by b.

int year = 2028;
if (year % 4 == 0) {
    System.out.println(year + " is divisible by 4");
}
for (int n = 1; n <= 15; n++) {
    if (n % 3 == 0 && n % 5 == 0) {
        System.out.print("both ");
    } else if (n % 3 == 0) {
        System.out.print("three ");
    } else if (n % 5 == 0) {
        System.out.print("five ");
    }
}
System.out.println();

Output:

2028 is divisible by 4
three five three three five three both 

The test for “divisible by both” comes first. If n % 3 == 0 came first, 15 would print “three” and never reach “both”.

Watch out: to test for odd numbers, write n % 2 != 0. In Java, -7 % 2 is -1, so n % 2 == 1 is false for negative odd numbers.

System.out.println(-7 % 2);
System.out.println(-7 % 2 != 0);

Output:

-1
true

2. The individual digits of an integer

There are standard algorithms to identify the individual digits in an integer 2.9.A.1. n % 10 is the last digit, and n / 10 (integer division) removes the last digit. Repeat while n > 0.

int n = 4072;
int digitSum = 0;
int digitCount = 0;
while (n > 0) {
    int digit = n % 10;
    System.out.println("digit: " + digit);
    digitSum += digit;
    digitCount++;
    n = n / 10;
}
System.out.println("sum " + digitSum + ", count " + digitCount);

Output:

digit: 2
digit: 7
digit: 0
digit: 4
sum 13, count 4

n at the check	n > 0	digit = n % 10	digitSum	n / 10
4072	true	2	2	407
407	true	7	9	40
40	true	0	9	4
4	true	4	13	0
0	false

Notes:

• The digits come out from right to left (ones digit first).
• The loop destroys n. Copy it first if you need the original value later.
• If n starts at 0, the loop runs zero times and digitCount stays 0. If the number 0 should count as one digit, handle it with an if before the loop.

The same pattern can build a number with the digits reversed:

int n = 1234;
int reversed = 0;
while (n > 0) {
    reversed = reversed * 10 + n % 10;
    n /= 10;
}
System.out.println(reversed);

Output:

4321

3. Frequency: how often a criterion is met

There are standard algorithms to determine the frequency with which a specific criterion is met 2.9.A.1. Pattern: set a counter to 0 before the loop, test each value with an if, add 1 when the test passes, use the counter after the loop.

How many numbers from 1 to 50 are divisible by 6 or by 8?

int count = 0;
for (int n = 1; n <= 50; n++) {
    if (n % 6 == 0 || n % 8 == 0) {
        count++;
    }
}
System.out.println(count);

Output:

12

There are 8 multiples of 6 and 6 multiples of 8 up to 50, but 24 and 48 are both, and || counts them only once: 8 + 6 - 2 = 12.

Watch out: writing int count = 0; inside the loop resets the counter every iteration, and the code would not compile here anyway, because count would not exist after the loop.

4. Minimum and maximum

There are standard algorithms to determine a minimum or maximum value 2.9.A.1. Pattern: keep the best value so far, and replace it whenever a new value beats it.

A shop sells a game at a price from 1 to 10 dollars. At price p, it expects to earn p * (100 - 8 * p) dollars. Which price earns the most?

int bestPrice = 1;
int bestIncome = 1 * (100 - 8 * 1);
for (int p = 2; p <= 10; p++) {
    int income = p * (100 - 8 * p);
    if (income > bestIncome) {
        bestIncome = income;
        bestPrice = p;
    }
}
System.out.println("Best price: " + bestPrice + ", income: " + bestIncome);

Output:

Best price: 6, income: 312

The minimum and maximum of the digits of a number use the same idea. Here the starting values come from the Java Quick Reference: Integer.MAX_VALUE is larger than any digit, and Integer.MIN_VALUE is smaller than any digit, so the first digit always replaces them.

int n = 58291;
int smallest = Integer.MAX_VALUE;
int largest = Integer.MIN_VALUE;
while (n > 0) {
    int d = n % 10;
    if (d < smallest) {
        smallest = d;
    }
    if (d > largest) {
        largest = d;
    }
    n /= 10;
}
System.out.println("min " + smallest + ", max " + largest);

Output:

min 1, max 9

Watch out: starting smallest at 0 would give a minimum of 0 for 58291, a digit it does not contain. Use two separate if statements (not if-else) when one value can update both the minimum and the maximum, as the first digit does here.

5. Sum and average

There are standard algorithms to compute a sum or average 2.9.A.1. Pattern: set the sum to 0 before the loop, add each value inside the loop, divide by the count after the loop. Cast to double to avoid integer division.

Average of the multiples of 7 between 1 and 40:

int sum = 0;
int count = 0;
for (int n = 1; n <= 40; n++) {
    if (n % 7 == 0) {
        sum += n;
        count++;
    }
}
System.out.println("sum " + sum + ", count " + count);
if (count != 0) {
    System.out.println(sum / count);
    double average = (double) sum / count;
    System.out.println(average);
}

Output:

sum 105, count 5
21
21.0

The multiples are 7, 14, 21, 28 and 35. Here the integer and the double averages agree, but try the digits of 4825: the sum is 19 and the count is 4, so 19 / 4 is 4 while (double) 19 / 4 is 4.75.

int sum = 19;
int count = 4;
System.out.println(sum / count);
System.out.println((double) sum / count);
System.out.println((double) (sum / count));

Output:

4
4.75
4.0

Watch out: (double) (sum / count) casts too late: the integer division has already thrown away the 0.75.

1. Traversing a string

String algorithms work by string traversal: a loop visits each position, and substring takes out the part to test. A single character at index i is str.substring(i, i + 1). Indexes run from 0 to length() - 1.

String team = "Hawks";
for (int i = 0; i < team.length(); i++) {
    System.out.println(i + ": " + team.substring(i, i + 1));
}

Output:

0: H
1: a
2: w
3: k
4: s

Watch out (off by one): with i <= team.length(), the last pass asks for substring(5, 6) on a 5-letter string:

String team = "Hawks";
for (int i = 0; i <= team.length(); i++) {
    System.out.println(team.substring(i, i + 1));
}

Output:

H
a
w
k
s
Exception in thread "main" java.lang.StringIndexOutOfBoundsException: Range [5, 6) out of bounds for length 5

The five letters print, then the program crashes on the sixth pass. (The exact wording of the message depends on the Java version.)

2. Does a substring have a property?

There are standard string algorithms to find if one or more substrings have a particular property 2.10.A.1. Two kinds of question:

• “Is there any substring with the property?” Return true as soon as you find one; return false only after the loop.
• “Do all substrings have the property?” Return false as soon as one fails; return true only after the loop.

Does a word contain a double letter (the same letter twice in a row)? Each test compares the letter at i with the letter at i + 1, so the loop must stop before the last index.

public static boolean hasDoubleLetter(String word) {
    for (int i = 0; i < word.length() - 1; i++) {
        String here = word.substring(i, i + 1);
        String next = word.substring(i + 1, i + 2);
        if (here.equals(next)) {
            return true;
        }
    }
    return false;
}

System.out.println(hasDoubleLetter("balloon"));
System.out.println(hasDoubleLetter("planet"));
System.out.println(hasDoubleLetter(""));

Output:

true
false
false

Watch out: putting else { return false; } inside the loop would make the method stop after checking only the first pair, so "balloon" would return false.

Is every character a digit? "0123456789".indexOf(ch) is -1 when ch is not a digit.

public static boolean allDigits(String code) {
    for (int i = 0; i < code.length(); i++) {
        String ch = code.substring(i, i + 1);
        if ("0123456789".indexOf(ch) == -1) {
            return false;
        }
    }
    return true;
}

System.out.println(allDigits("2026"));
System.out.println(allDigits("20x6"));

Output:

true
false

3. Counting substrings that meet a criterion

There are standard string algorithms to determine the number of substrings that meet specific criteria 2.10.A.1. Count the vowels in a sentence:

String sentence = "Game over";
int vowels = 0;
for (int i = 0; i < sentence.length(); i++) {
    String ch = sentence.substring(i, i + 1);
    if ("aeiouAEIOU".indexOf(ch) >= 0) {
        vowels++;
    }
}
System.out.println("Vowels: " + vowels);

Output:

Vowels: 4

To count a pattern longer than one letter, use a window of that length. How many times does "an" appear in "banana"? The window substring(i, i + 2) needs i + 2 <= length(), so the loop condition is i <= word.length() - 2.

String word = "banana";
int count = 0;
for (int i = 0; i <= word.length() - 2; i++) {
    if (word.substring(i, i + 2).equals("an")) {
        count++;
    }
}
System.out.println(count);

Output:

2

i	substring(i, i + 2)	equals “an”?	count
0	ba	no	0
1	an	yes	1
2	na	no	1
3	an	yes	2
4	na	no	2

Watch out (String comparison with ==): this version compiles and runs, but == compares references, and every call to substring here returns a new String object.

String word = "banana";
int count = 0;
for (int i = 0; i < word.length(); i++) {
    if (word.substring(i, i + 1) == "a") {
        count++;
    }
}
System.out.println(count);

Output:

0

4. Reversing a string

There are standard string algorithms to create a new string with the characters reversed 2.10.A.1. Strings are immutable, so you build a new string. Adding each character to the front reverses the order:

String word = "code";
String reversed = "";
for (int i = 0; i < word.length(); i++) {
    reversed = word.substring(i, i + 1) + reversed;
}
System.out.println(reversed);

Output:

edoc

i	letter	reversed after this iteration
0	c	c
1	o	oc
2	d	doc
3	e	edoc

The other way: traverse from the last index down to 0 and add each character to the end. Start at length() - 1, not length().

String word = "code";
String reversed = "";
for (int i = word.length() - 1; i >= 0; i--) {
    reversed += word.substring(i, i + 1);
}
System.out.println(reversed);

Output:

edoc

5. Combining the algorithms

Original algorithms often combine the standard ones. A palindrome reads the same forward and backward: reverse the word, then compare with equals.

public static boolean isPalindrome(String word) {
    String reversed = "";
    for (int i = 0; i < word.length(); i++) {
        reversed = word.substring(i, i + 1) + reversed;
    }
    return reversed.equals(word);
}

System.out.println(isPalindrome("level"));
System.out.println(isPalindrome("lever"));

Output:

true
false

Another combination: remove every space from a string by building a new one that skips spaces.

String phrase = "a b  c";
String result = "";
for (int i = 0; i < phrase.length(); i++) {
    String ch = phrase.substring(i, i + 1);
    if (!ch.equals(" ")) {
        result += ch;
    }
}
System.out.println(result + " (" + result.length() + " letters)");

Output:

abc (3 letters)

1. A loop inside a loop

A nested iteration statement is a loop placed inside the body of another loop. The order is strict: once the inner loop starts, it finishes every one of its iterations, and only then can the outer loop go on to its next iteration 2.11.A.1.

for (int round = 1; round <= 2; round++) {
    for (int player = 1; player <= 3; player++) {
        System.out.println("Round " + round + ", player " + player);
    }
    System.out.println("End of round " + round);
}

Output:

Round 1, player 1
Round 1, player 2
Round 1, player 3
End of round 1
Round 2, player 1
Round 2, player 2
Round 2, player 3
End of round 2

The inner loop ran all 3 players before the outer loop moved from round 1 to round 2, and it started again at player 1 in round 2. The inner body ran 2 times 3 = 6 times.

2. Rows and columns

Think of the outer loop as rows and the inner loop as columns. print stays on the same line; println after the inner loop ends the row.

for (int row = 1; row <= 3; row++) {
    for (int col = 1; col <= 4; col++) {
        System.out.print(row * col + " ");
    }
    System.out.println();
}

Output:

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

Watch out: a per-row result must be reset inside the outer loop. This code totals each row of the table above:

for (int row = 1; row <= 3; row++) {
    int rowTotal = 0;
    for (int col = 1; col <= 4; col++) {
        rowTotal += row * col;
    }
    System.out.println("Row " + row + " total: " + rowTotal);
}

Output:

Row 1 total: 10
Row 2 total: 20
Row 3 total: 30

If int rowTotal = 0; were moved above the outer loop, the totals would pile up: 10, 30, 60.

3. Inner bounds that depend on the outer loop

When the inner loop’s Boolean expression uses the outer loop control variable, each row has a different length. A triangle:

for (int i = 1; i <= 4; i++) {
    for (int j = 1; j <= i; j++) {
        System.out.print("*");
    }
    System.out.println();
}

Output:

*
**
***
****

i	inner loop values of j	stars printed
1	1	1
2	1, 2	2
3	1, 2, 3	3
4	1, 2, 3, 4	4

The inner body ran 1 + 2 + 3 + 4 = 10 times. Changing the inner loop to start at j = i and run while j <= 4 would print the rows in the other order: 4, 3, 2, 1 stars.

A number pattern built the same way:

for (int i = 1; i <= 3; i++) {
    for (int j = i; j <= 3; j++) {
        System.out.print(j);
    }
    System.out.println();
}

Output:

123
23
3

4. Checking pairs in a string

Nested loops can compare every character with every later character. Does a code contain any repeated letter? The inner loop starts at j = i + 1, so each pair is checked once and no letter is compared with itself.

String code = "PLANET";
boolean repeat = false;
for (int i = 0; i < code.length(); i++) {
    for (int j = i + 1; j < code.length(); j++) {
        if (code.substring(i, i + 1).equals(code.substring(j, j + 1))) {
            repeat = true;
        }
    }
}
System.out.println("Repeat: " + repeat);

Output:

Repeat: false

With "LETTER" instead, the code prints Repeat: true (E and T both repeat). For a 6-letter string the inner body runs 5 + 4 + 3 + 2 + 1 = 15 times.

A while loop can be nested in a for loop too. Count the digits of each number from 8 to 12:

for (int n = 8; n <= 12; n++) {
    int temp = n;
    int digits = 0;
    while (temp > 0) {
        digits++;
        temp /= 10;
    }
    System.out.print(digits + " ");
}
System.out.println();

Output:

1 1 2 2 2 

The copy temp matters: dividing n itself would change the outer loop control variable and break the outer loop.

5. Common nested loop errors

Using the same name for both loop control variables does not compile when both are declared in their headers:

for (int i = 0; i < 3; i++) {
    for (int i = 0; i < 2; i++) {
        System.out.print(i);
    }
}

error: variable i is already defined in method main(String[])

Using the outer variable in the inner header by mistake (j < i when you meant j < 3) changes how many times the inner body runs. The first row can even run zero times:

int count = 0;
for (int i = 0; i < 3; i++) {
    for (int j = 0; j < i; j++) {
        count++;
    }
}
System.out.println(count);

Output:

3

With j < 3 the count would be 9. Here the inner loop runs 0, 1 and 2 times. To check nested loops, write a small table with one row per outer iteration and list what the inner loop does in that row.

1. What a statement execution count is

A statement execution count tells you how many times a statement is executed by the program. You usually calculate it informally, by tracing and analyzing the iterative statements 2.12.A.1. A counter variable can check your count, but on the exam you work it out by reasoning.

int total = 0;
for (int i = 0; i < 5; i++) {
    total += i;
}
System.out.println(total);

Output:

10

Statement	Executions	Why
int total = 0;	1	before the loop
int i = 0	1	initialization runs once
i < 5	6	true for i = 0 to 4, false for i = 5
total += i;	5	once per iteration
i++	5	after each iteration
System.out.println(total);	1	after the loop

2. Counting a single loop quickly

Find the number of iterations, then the body count follows. Trace the first value, the last value that passes the check, and the step.

Loop header	Values	Body executions
for (int i = 0; i < n; i++)	0 to n - 1	n
for (int i = 1; i <= n; i++)	1 to n	n
for (int i = 0; i <= n; i++)	0 to n	n + 1
for (int i = 2; i < n; i++)	2 to n - 1	n - 2
for (int i = 0; i < n; i += 2)	0, 2, 4, …	n / 2, rounded up

A statement inside an if runs only when the condition is true:

int printed = 0;
for (int k = 1; k <= 20; k++) {
    if (k % 3 == 0) {
        System.out.print(k + " ");
        printed++;
    }
}
System.out.println();
System.out.println("print ran " + printed + " times");

Output:

3 6 9 12 15 18 
print ran 6 times

The loop body (the if test) ran 20 times, but the print ran only 6 times: once for each multiple of 3 from 1 to 20.

3. Loops that double or halve

When the loop control variable doubles or halves, the count grows very slowly as the bound grows.

int n = 100;
int count = 0;
for (int i = 1; i < n; i *= 2) {
    count++;
}
System.out.println(count);

Output:

7

The values of i are 1, 2, 4, 8, 16, 32, 64, so the body runs 7 times. If n were 1000, the body would run only 10 times. A while loop that halves its variable behaves the same way:

int size = 1000;
int halvings = 0;
while (size > 1) {
    size /= 2;
    halvings++;
}
System.out.println(halvings);

Output:

9

size goes 1000, 500, 250, 125, 62, 31, 15, 7, 3, 1 (integer division), which is 9 halvings.

4. Nested loops: multiply or add up

Sequential loops add their counts; nested loops multiply them when the bounds are fixed.

int n = 4;
int a = 0;
int b = 0;
for (int i = 0; i < n; i++) {
    a++;
}
for (int j = 0; j < n; j++) {
    a++;
}
for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        b++;
    }
}
System.out.println("sequential: " + a + ", nested: " + b);

Output:

sequential: 8, nested: 16

When the inner bound depends on the outer variable, add the inner count for each outer iteration:

int n = 5;
int count = 0;
for (int i = 0; i < n; i++) {
    for (int j = 0; j < i; j++) {
        count++;
    }
}
System.out.println(count);

Output:

10

i	inner iterations (j < i)
0	0
1	1
2	2
3	3
4	4
total	0 + 1 + 2 + 3 + 4 = 10

In general this shape runs n(n - 1) / 2 times. A statement placed after the inner loop but inside the outer loop runs only n times.

5. Comparing run times informally

Two code segments can produce the same result with very different execution counts. Comparing the counts is an informal run-time comparison 2.12.A.1. Both segments below count the divisors of 36.

Segment A tests every number from 1 to 36:

int n = 36;
int divisors = 0;
int checks = 0;
for (int d = 1; d <= n; d++) {
    checks++;
    if (n % d == 0) {
        divisors++;
    }
}
System.out.println(divisors + " divisors, " + checks + " checks");

Output:

9 divisors, 36 checks

Segment B only tests up to the square root, because divisors come in pairs (2 and 18, 3 and 12…):

int n = 36;
int divisors = 0;
int checks = 0;
for (int d = 1; d * d <= n; d++) {
    checks++;
    if (n % d == 0) {
        if (d * d == n) {
            divisors++;
        } else {
            divisors += 2;
        }
    }
}
System.out.println(divisors + " divisors, " + checks + " checks");

Output:

9 divisors, 6 checks

Same answer, 6 checks instead of 36. For n = 1,000,000, Segment A would make 1,000,000 checks and Segment B only 1,000. The segment with the smaller statement execution count for large inputs has the better run time.