Loading…

easyMath GeometrySometimes asked

Handshake

Q: How do you solve Handshake using the Brute Force — Count Pairs with a Double Loop approach?

When to use it: Use to make the counting concrete and derive the formula, then collapse it to O(1). Count the handshakes the way you'd tally them by hand. **The double loop.** For each director `i`, pair them with every later director `j > i` and increment a counter. Starting `j` at `i + 1` ensures each unordered pair is counted exactly once and never pairs someone with themselves — the same loop-invariant trick as in pair-finding problems. **What the count reveals.** Director 0 shakes with n−1 others, director 1 with n−2 *new* others, and so on down to the last director who shakes 0 new hands. The total is `(n−1) + (n−2) + … + 1 + 0`, the sum of the first n−1 integers, which equals `n(n−1)/2`. That derivation is exactly the closed form — the loop is just the slow way to evaluate it. **Why we don't ship it.** For n up to 10⁶ a double loop is ~10¹² operations — far too slow, and pointless when the sum has a one-line formula. Show the loop to *derive* the answer, then state the formula. Time complexity: O(n²). Space complexity: O(1).

Q: How do you solve Handshake using the Closed Form — C(n, 2) = n(n−1)/2 (Optimal) approach?

When to use it: The expected answer. Phrase it as 'choose 2 of n, so C(n,2) = n(n−1)/2 in O(1)'. Replace the loop with the combinatorial identity it computes. **Why it's a combination.** A handshake is an unordered choice of 2 distinct directors from n. The number of such choices is `C(n, 2)`. Expanding, `C(n, 2) = n(n−1)/2`. **Why divide by 2.** If you first count *ordered* pairs you get `n(n−1)` (each of n people shakes with the other n−1). But A-shakes-B and B-shakes-A are the same handshake, so every handshake is counted twice — dividing by 2 corrects the double count. Forgetting the `/2` is the single most common error and gives exactly twice the right answer. **Why the integer division is exact.** Among any two consecutive integers `n` and `n−1`, one is even, so their product `n(n−1)` is even and `n(n−1)/2` has no remainder. There's no need for floating-point. **Overflow.** For `n = 10⁶`, `n(n−1) ≈ 10¹²` overflows a 32-bit `int`. Compute the product in a 64-bit type (`long`) before dividing. **Boundaries.** `n = 0` → 0, `n = 1` → 0, both produced directly by the formula with no special casing. Time complexity: O(1). Space complexity: O(1).

Math & Number Theory · 34 of 36 · 6 min

At the annual meeting of Board of Directors of a company, every two directors shake hands exactly once. Given the number of directors n, determine the total number of handshakes that take place.

For each of t test cases, you are given an integer n and must output the handshake count.

In plain English

Each handshake involves exactly two distinct people and a pair shakes only once, so handshakes correspond one-to-one with unordered pairs from the n directors. Counting unordered pairs of n items is the combination C(n, 2) = n·(n−1)/2. There is no enumeration to do — it's a direct formula, evaluated in constant time.

Examples

Example 1

Input: n = 1
Output: 0
Note: A single director has no one to shake hands with: 1·0/2 = 0.

Example 2

Input: n = 2
Output: 1
Note: Exactly one pair: 2·1/2 = 1.

Example 3

Input: n = 3
Output: 3
Note: Pairs {1,2}, {1,3}, {2,3}: 3·2/2 = 3.

Constraints

1 ≤ t ≤ 1000 (number of test cases)
0 ≤ n ≤ 10⁶ per test case
Each pair shakes hands exactly once
Order does not matter (A↔B is a single handshake)
The answer can exceed a 32-bit integer for large n

Clarifying questions4First question: Does the order of a handshake matter — is A shaking B different from B shaking A?Explore questions

Q1.Does the order of a handshake matter — is A shaking B different from B shaking A?
No, a handshake is mutual, so {A, B} is one event. That's why we count combinations (divide by 2), not ordered pairs.
Q2.Can a person shake their own hand?
No self-handshakes. We pick 2 distinct people, which is why the count is n·(n−1)/2, not n².
Q3.What should the answer be for n = 0 or n = 1?
0 — with fewer than two people no handshake can occur, and the formula naturally gives 0.
Q4.Could the result overflow a 32-bit integer?
Yes for large n (e.g. n = 10⁶ gives ~5×10¹¹). Use a 64-bit type to hold the product before dividing.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

At a board meeting of `n` executives, each pair shakes hands exactly once; count the total handshakes. Every handshake is an unordered pair of distinct people, so the answer is the number of 2-combinations: C(n, 2) = n·(n−1)/2. Compute it in O(1) with `n * (n - 1) / 2` — and use integer arithmetic (one of n, n−1 is even, so the division is exact). For n = 0 or 1 the answer is 0.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you recognise 'every pair shakes once' as the combination C(n,2) and give the O(1) closed form n(n−1)/2 instead of an O(n²) simulation, with correct integer division and overflow awareness.

Where candidates slip

Returning n·(n−1) (forgetting to divide by 2, i.e. counting each handshake twice) or n² (counting self-pairs and ordered pairs), or overflowing a 32-bit int for large n.

How to stand out

Derive the formula two ways — sum 1+2+…+(n−1) for the i-th arrival, and C(n,2) — note the division is always exact, and flag the need for 64-bit arithmetic at scale.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Brute Force — Count Pairs with a Double Loop	`O(n²)`	`O(1)`	Use to make the counting concrete and derive the formula, then collapse it to O(1).	Read
2	Closed Form — C(n, 2) = n(n−1)/2 (Optimal)Optimal	`O(1)`	`O(1)`	The expected answer. Phrase it as 'choose 2 of n, so C(n,2) = n(n−1)/2 in O(1)'.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewCount handshakes among nOrder matter?YesNoExplore the full tree

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Brute Force — Count Pairs with a Double Loop

TimeO(n²)SpaceO(1)

Use to make the counting concrete and derive the formula, then collapse it to O(1).

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Every handshake is a pair (i, j) with i < j. Count them directly.

2Hint 2Explore hint

Two nested loops: outer i from 0 to n−1, inner j from i+1 to n−1, incrementing a counter each time.

3Hint 3Explore hint

The counter ends at the total number of pairs. Observe the count equals 1+2+…+(n−1) — that's the seed of the closed form.

A · Core idea

Count the handshakes the way you'd tally them by hand.

The double loop. For each director i, pair them with every later director j > i and increment a counter. Starting j at i + 1 ensures each unordered pair is counted exactly once and never pairs someone with themselves — the same loop-invariant trick as in pair-finding problems.

What the count reveals. Director 0 shakes with n−1 others, director 1 with n−2 new others, and so on down to the last director who shakes 0 new hands. The total is (n−1) + (n−2) + … + 1 + 0, the sum of the first n−1 integers, which equals n(n−1)/2. That derivation is exactly the closed form — the loop is just the slow way to evaluate it.

Why we don't ship it. For n up to 10⁶ a double loop is ~10¹² operations — far too slow, and pointless when the sum has a one-line formula. Show the loop to derive the answer, then state the formula.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

n = 3

Interactive diagram

Pairs as edges of K₃

i=0

Active call / nodeSupporting contextReturned stateNot active

Three people form three handshakes — the edges of a triangle (complete graph K₃).

Final result3

C · Code with teaching comments

Reference implementation previewpublic long handshake(int n) { long count = 0; for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { // each unordered pair once count++;Explore the full code

solution.javaJava

Brute Force — Count Pairs with a Double Loop — reference

2 teaching notes

1
public long handshake(int n) {
2
    long count = 0;
3
    for (int i = 0; i < n; i++) {
4
        // Starting j at i+1 avoids self-pairs and counting {i,j} and {j,i} twice.
5
        for (int j = i + 1; j < n; j++) {   // each unordered pair once
6
            // One increment per distinct pair — the running handshake tally.
7
            count++;
8
        }
9
    }
10
    return count;
11
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.11 lines

D · Why it works and complexityO(n²) timeO(1) spaceOpen the invariant and proofExplore the proof

Summing 'new handshakes per arriving person' gives 1+2+…+(n−1) = n(n−1)/2 — the arithmetic-series identity is the bridge from the O(n²) loop to the O(1) formula.

ComplexityO(n²) time, O(1) space — The nested loops perform n(n−1)/2 increments, which is Θ(n²) operations; constant extra space.

E · Edge cases and pitfalls3Starting j at 0 — counts self-pairs and each handshake twice.Explore edge cases

Pitfalls

Starting j at 0 — counts self-pairs and each handshake twice.
O(n²) is far too slow for n up to 10⁶.
Using a 32-bit counter — overflows for large n.

03.2

Approach 2 of 2 · Optimal

Closed Form — C(n, 2) = n(n−1)/2 (Optimal)

TimeO(1)SpaceO(1)

The expected answer. Phrase it as 'choose 2 of n, so C(n,2) = n(n−1)/2 in O(1)'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Each handshake is an unordered pair of distinct people, so the count is the number of 2-combinations of n: C(n, 2).

2Hint 2Explore hint

C(n, 2) = n!/(2!(n−2)!) = n(n−1)/2.

3Hint 3Explore hint

Evaluate `n * (n - 1) / 2` with 64-bit integers. The product n(n−1) is always even, so integer division is exact.

A · Core idea

Replace the loop with the combinatorial identity it computes.

Why it's a combination. A handshake is an unordered choice of 2 distinct directors from n. The number of such choices is C(n, 2). Expanding, C(n, 2) = n(n−1)/2.

Why divide by 2. If you first count ordered pairs you get n(n−1) (each of n people shakes with the other n−1). But A-shakes-B and B-shakes-A are the same handshake, so every handshake is counted twice — dividing by 2 corrects the double count. Forgetting the /2 is the single most common error and gives exactly twice the right answer.

Why the integer division is exact. Among any two consecutive integers n and n−1, one is even, so their product n(n−1) is even and n(n−1)/2 has no remainder. There's no need for floating-point.

Overflow. For n = 10⁶, n(n−1) ≈ 10¹² overflows a 32-bit int. Compute the product in a 64-bit type (long) before dividing.

Boundaries. n = 0 → 0, n = 1 → 0, both produced directly by the formula with no special casing.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

n = 5

Ordered pairs ÷ 2 = handshakes

How to read it:n(n−1) counts directed pairs; dividing by 2 removes the A↔B double count.

Rendering diagram…

Final result10

C · Code with teaching comments

solution.javaJava

Closed Form — C(n, 2) = n(n−1)/2 (Optimal) — optimal

1 teaching note

1
public long handshake(int n) {
2
    // Cast n to long so the product is computed in 64 bits; n(n−1) is even so /2 is
3
    // exact.
4
    return (long) n * (n - 1) / 2;        // C(n,2); cast to avoid 32-bit overflow
5
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.5 lines

D · Why it works and complexityO(1) timeO(1) spaceOpen the invariant and proofExplore the proof

The same n(n−1)/2 counts the edges of a complete graph K_n and the games in a round-robin tournament. Spotting 'every pair, once' as C(n,2) is the reusable move that turns an O(n²) tally into a one-liner.

ComplexityO(1) time, O(1) space — A single multiplication and division — constant time and space, independent of n.

E · Edge cases and pitfalls6n = 0 — 0·(−1)/2 = 0 — no people, no handshakes.Explore edge cases

Edge cases handled

n = 00·(−1)/2 = 0 — no people, no handshakes.
n = 11·0/2 = 0 — one person can't shake hands.
n = 10⁶≈ 4.999995×10¹¹ — exceeds 32-bit range, so a 64-bit type is required.

Pitfalls

Returning n·(n−1) without the /2 — double counts every handshake.
Returning n² — counts self-pairs and ordered pairs.
Computing n*(n-1) in a 32-bit int before casting — overflow for large n.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic long handshake(int n) { return (long) n * (n - 1) / 2; // C(n,2); cast to avoid 32-bit overflow }Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Missing the divide-by-two

n(n−1) counts ordered pairs; each handshake (A↔B) appears as both (A,B) and (B,A). Dividing by 2 collapses them.

Explore the code comparison

Don't write this

return n * (n - 1)        # double counts each handshake

Write this instead

return n * (n - 1) // 2

32-bit overflow

For n = 10⁶, n(n−1) ≈ 10¹² exceeds the ~2.1×10⁹ limit of a 32-bit int, silently wrapping to a wrong value.

Explore the code comparison

Don't write this

int result = n * (n - 1) / 2;       // overflow before division

Write this instead

long result = (long) n * (n - 1) / 2;

Using n² (self/ordered pairs)

n² counts every ordered pair including a person with themselves, which isn't a handshake. The correct count excludes self-pairs and halves the rest.

Explore the code comparison

Don't write this

return n * n              # includes self-pairs and double counts

Write this instead

return n * (n - 1) // 2

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Count unordered pairs → C(n,2) = n(n−1)/2 closed form

Code pattern to memorize

handshakes = n * (n - 1) / 2     # integer division is exact

Rules to remember

1The answer is C(n, 2) = n·(n−1)/2 — the number of unordered pairs of n people.
2Use integer division: among n and n−1 one is always even, so n*(n-1) is even and /2 is exact.
3For n = 0 or n = 1 the formula yields 0 — no handshakes possible.
4Watch overflow: for large n, n*(n-1) may exceed 32 bits — use a 64-bit type.
5Order doesn't matter (A↔B is one handshake), which is exactly why it's a combination, not a permutation.

Use this pattern when

Counting unordered pairs / edges among n items (handshakes, matches, chords)
Number of edges in a complete graph K_n
Any 'how many ways to pick 2 of n' question
Replacing a double loop of pair-counting with a formula

Choose another pattern when

Order matters (A→B ≠ B→A) → that's permutations n·(n−1), not divided by 2
Pairs may repeat or self-pairs allowed → adjust the combinatorial model
You must enumerate the actual pairs, not count them → nested loop is required
Choosing k > 2 items → general C(n, k), not this special case

Interview takeaway

Handshake is the textbook C(n,2): each unordered pair shakes once, giving n(n−1)/2. Recognising 'count unordered pairs' as a combination collapses a double loop into an O(1) formula — the same n(n−1)/2 counts edges of a complete graph and matches in a round-robin.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternCombinatorial counting: 'every pair exactly once' is C(n,2) = n(n−1)/2. Recognising unordered-pair counts as combinations turns an O(n²) tally into an O(1) formula. The same value counts edges of a complete graph K_n and round-robin matches.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Same pattern

←

Number Line Jumps

Continue · Next problem

Recursive Digit Sum

easyMath GeometrySometimes asked

Handshake

Math & Number Theory · 34 of 36 · 6 min

For each of t test cases, you are given an integer n and must output the handshake count.

In plain English

Examples

Example 1

Input: n = 1
Output: 0
Note: A single director has no one to shake hands with: 1·0/2 = 0.

Example 2

Input: n = 2
Output: 1
Note: Exactly one pair: 2·1/2 = 1.

Example 3

Input: n = 3
Output: 3
Note: Pairs {1,2}, {1,3}, {2,3}: 3·2/2 = 3.

Constraints

1 ≤ t ≤ 1000 (number of test cases)
0 ≤ n ≤ 10⁶ per test case
Each pair shakes hands exactly once
Order does not matter (A↔B is a single handshake)
The answer can exceed a 32-bit integer for large n

Clarifying questions4First question: Does the order of a handshake matter — is A shaking B different from B shaking A?Explore questions

Q1.Does the order of a handshake matter — is A shaking B different from B shaking A?
No, a handshake is mutual, so {A, B} is one event. That's why we count combinations (divide by 2), not ordered pairs.
Q2.Can a person shake their own hand?
No self-handshakes. We pick 2 distinct people, which is why the count is n·(n−1)/2, not n².
Q3.What should the answer be for n = 0 or n = 1?
0 — with fewer than two people no handshake can occur, and the formula naturally gives 0.
Q4.Could the result overflow a 32-bit integer?
Yes for large n (e.g. n = 10⁶ gives ~5×10¹¹). Use a 64-bit type to hold the product before dividing.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Where candidates slip

Returning n·(n−1) (forgetting to divide by 2, i.e. counting each handshake twice) or n² (counting self-pairs and ordered pairs), or overflowing a 32-bit int for large n.

How to stand out

Derive the formula two ways — sum 1+2+…+(n−1) for the i-th arrival, and C(n,2) — note the division is always exact, and flag the need for 64-bit arithmetic at scale.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Brute Force — Count Pairs with a Double Loop	`O(n²)`	`O(1)`	Use to make the counting concrete and derive the formula, then collapse it to O(1).	Read
2	Closed Form — C(n, 2) = n(n−1)/2 (Optimal)Optimal	`O(1)`	`O(1)`	The expected answer. Phrase it as 'choose 2 of n, so C(n,2) = n(n−1)/2 in O(1)'.	Read

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Brute Force — Count Pairs with a Double Loop

TimeO(n²)SpaceO(1)

Use to make the counting concrete and derive the formula, then collapse it to O(1).

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Every handshake is a pair (i, j) with i < j. Count them directly.

2Hint 2Explore hint

Two nested loops: outer i from 0 to n−1, inner j from i+1 to n−1, incrementing a counter each time.

3Hint 3Explore hint

The counter ends at the total number of pairs. Observe the count equals 1+2+…+(n−1) — that's the seed of the closed form.

A · Core idea

Count the handshakes the way you'd tally them by hand.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

n = 3

Interactive diagram

Pairs as edges of K₃

i=0

Active call / nodeSupporting contextReturned stateNot active

Three people form three handshakes — the edges of a triangle (complete graph K₃).

Final result3

C · Code with teaching comments

solution.javaJava

Brute Force — Count Pairs with a Double Loop — reference

2 teaching notes

1
public long handshake(int n) {
2
    long count = 0;
3
    for (int i = 0; i < n; i++) {
4
        // Starting j at i+1 avoids self-pairs and counting {i,j} and {j,i} twice.
5
        for (int j = i + 1; j < n; j++) {   // each unordered pair once
6
            // One increment per distinct pair — the running handshake tally.
7
            count++;
8
        }
9
    }
10
    return count;
11
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.11 lines

D · Why it works and complexityO(n²) timeO(1) spaceOpen the invariant and proofExplore the proof

Summing 'new handshakes per arriving person' gives 1+2+…+(n−1) = n(n−1)/2 — the arithmetic-series identity is the bridge from the O(n²) loop to the O(1) formula.

ComplexityO(n²) time, O(1) space — The nested loops perform n(n−1)/2 increments, which is Θ(n²) operations; constant extra space.

E · Edge cases and pitfalls3Starting j at 0 — counts self-pairs and each handshake twice.Explore edge cases

Pitfalls

Starting j at 0 — counts self-pairs and each handshake twice.
O(n²) is far too slow for n up to 10⁶.
Using a 32-bit counter — overflows for large n.

03.2

Approach 2 of 2 · Optimal

Closed Form — C(n, 2) = n(n−1)/2 (Optimal)

TimeO(1)SpaceO(1)

The expected answer. Phrase it as 'choose 2 of n, so C(n,2) = n(n−1)/2 in O(1)'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Each handshake is an unordered pair of distinct people, so the count is the number of 2-combinations of n: C(n, 2).

2Hint 2Explore hint

C(n, 2) = n!/(2!(n−2)!) = n(n−1)/2.

3Hint 3Explore hint

Evaluate `n * (n - 1) / 2` with 64-bit integers. The product n(n−1) is always even, so integer division is exact.

A · Core idea

Replace the loop with the combinatorial identity it computes.

Why it's a combination. A handshake is an unordered choice of 2 distinct directors from n. The number of such choices is C(n, 2). Expanding, C(n, 2) = n(n−1)/2.

Overflow. For n = 10⁶, n(n−1) ≈ 10¹² overflows a 32-bit int. Compute the product in a 64-bit type (long) before dividing.

Boundaries. n = 0 → 0, n = 1 → 0, both produced directly by the formula with no special casing.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

n = 5

Ordered pairs ÷ 2 = handshakes

How to read it:n(n−1) counts directed pairs; dividing by 2 removes the A↔B double count.

Rendering diagram…

Final result10

C · Code with teaching comments

solution.javaJava

Closed Form — C(n, 2) = n(n−1)/2 (Optimal) — optimal

1 teaching note

1
public long handshake(int n) {
2
    // Cast n to long so the product is computed in 64 bits; n(n−1) is even so /2 is
3
    // exact.
4
    return (long) n * (n - 1) / 2;        // C(n,2); cast to avoid 32-bit overflow
5
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.5 lines

D · Why it works and complexityO(1) timeO(1) spaceOpen the invariant and proofExplore the proof

ComplexityO(1) time, O(1) space — A single multiplication and division — constant time and space, independent of n.

E · Edge cases and pitfalls6n = 0 — 0·(−1)/2 = 0 — no people, no handshakes.Explore edge cases

Edge cases handled

n = 00·(−1)/2 = 0 — no people, no handshakes.
n = 11·0/2 = 0 — one person can't shake hands.
n = 10⁶≈ 4.999995×10¹¹ — exceeds 32-bit range, so a 64-bit type is required.

Pitfalls

Returning n·(n−1) without the /2 — double counts every handshake.
Returning n² — counts self-pairs and ordered pairs.
Computing n*(n-1) in a 32-bit int before casting — overflow for large n.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic long handshake(int n) { return (long) n * (n - 1) / 2; // C(n,2); cast to avoid 32-bit overflow }Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Missing the divide-by-two

n(n−1) counts ordered pairs; each handshake (A↔B) appears as both (A,B) and (B,A). Dividing by 2 collapses them.

Explore the code comparison

Don't write this

return n * (n - 1)        # double counts each handshake

Write this instead

return n * (n - 1) // 2

32-bit overflow

For n = 10⁶, n(n−1) ≈ 10¹² exceeds the ~2.1×10⁹ limit of a 32-bit int, silently wrapping to a wrong value.

Explore the code comparison

Don't write this

int result = n * (n - 1) / 2;       // overflow before division

Write this instead

long result = (long) n * (n - 1) / 2;

Using n² (self/ordered pairs)

n² counts every ordered pair including a person with themselves, which isn't a handshake. The correct count excludes self-pairs and halves the rest.

Explore the code comparison

Don't write this

return n * n              # includes self-pairs and double counts

Write this instead

return n * (n - 1) // 2

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Count unordered pairs → C(n,2) = n(n−1)/2 closed form

Code pattern to memorize

handshakes = n * (n - 1) / 2     # integer division is exact

Rules to remember

1The answer is C(n, 2) = n·(n−1)/2 — the number of unordered pairs of n people.
2Use integer division: among n and n−1 one is always even, so n*(n-1) is even and /2 is exact.
3For n = 0 or n = 1 the formula yields 0 — no handshakes possible.
4Watch overflow: for large n, n*(n-1) may exceed 32 bits — use a 64-bit type.
5Order doesn't matter (A↔B is one handshake), which is exactly why it's a combination, not a permutation.

Use this pattern when

Counting unordered pairs / edges among n items (handshakes, matches, chords)
Number of edges in a complete graph K_n
Any 'how many ways to pick 2 of n' question
Replacing a double loop of pair-counting with a formula

Choose another pattern when

Order matters (A→B ≠ B→A) → that's permutations n·(n−1), not divided by 2
Pairs may repeat or self-pairs allowed → adjust the combinatorial model
You must enumerate the actual pairs, not count them → nested loop is required
Choosing k > 2 items → general C(n, k), not this special case

Interview takeaway

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Same pattern

←

Number Line Jumps

Continue · Next problem

Recursive Digit Sum