Start learning free

LESSON 53 OF 338 · CALCULATIONS - CHALLENGES

Hand Shakes in Go: A Formula Instead of a Loop

Practice Read the full explanation

There are n friends in a group. When they meet, everybody shakes hands with everybody. How many hand shakes happen?

Example:

Input: n = 3

Output: 3

Explanation:
Considering A, B, and C are the 3 friends.
The hand shakes are: (A, B), (A, C) and (B, C)
Hints:

Take an example with n = 4 and write down all the hand shakes as in the explanation above. What do you notice?

Hopefully you wrote the following pairs: (A, B), (A, C), (A, D), (B, C), (B, D), (C, D)
How many hand shakes are there of the form (A, X) ? What about (B, X) ?

(A, B), (A, C), (A, D)
(B, C), (B, D)
(C, D)
We have 3 hand shakes that start with A
We have 2 hand shakes that start with B
And 1 hand shake that start with C
In total we have 3 + 2 + 1 = 6
Can you come up with a formula for this?

Let's put the first letter of each handshake in a square:
A A A O
B B O O
C O O O
O O O O

Notice that the last row is empty, so we should remove that:
A A A O
B B O O
C O O O

In this rectangle we have 6 empty and 6 filled (the hand shakes)
This means that our answer is the area of rectangle / 2


Let's recap. For n = 4 we have a rectangle with (n - 1) rows and n columns.
Our answer is the area / 2.
The area for the rectangle is (n - 1) * n
Therefore the full answer is ((n - 1) * n) / 2
STEP 1 OF 1
    Ctrl + Enter to check

    GO · CALCULATIONS - CHALLENGES

    Hand Shakes in Go, explained

    Problem overview

    There are n friends and everybody shakes hands with everybody else, once per pair. The function countHandShakes returns how many handshakes happen.

    For n = 3, call the friends A, B and C. The handshakes are (A, B), (A, C) and (B, C), so the answer is 3.

    Approach

    You could count by simulation: for each friend, loop over the friends after them and add one for each pair. That works, but it takes a number of steps that grows with the square of n. Counting carefully gives a formula that needs a single calculation.

    Write out the pairs for n = 4, with friends A, B, C and D:

    (A, B) (A, C) (A, D)
(B, C) (B, D)
(C, D)

    A shakes hands with 3 people who come after A, B with 2 and C with 1. The total is 3 + 2 + 1 = 6. In general the total is (n - 1) + (n - 2) + ... + 1, and there is a shortcut for it.

    Counting each handshake twice

    Each of the n people shakes hands with the other n - 1 people. That gives n * (n - 1) handshakes, but every handshake has been counted twice: once from each of the two people involved. Divide by 2 to count each one once:

    n * (n - 1) / 2

    For n = 4 this is 4 * 3 / 2 = 6, matching the list above.

    Seeing it as a rectangle

    Write the first member of each pair as a mark in a grid with n - 1 rows and n columns. Row by row the filled cells make a staircase of 3, 2 and 1 handshakes for four friends, and the empty cells make a second staircase of the same size that fits into the other half. So the filled cells are exactly half of the rectangle, which has (n - 1) * n cells. This is the same formula, reached by a picture.

    Step by step

    1. Take the number of friends as the parameter n.
    2. Multiply n by n - 1 to count ordered pairs, where (A, B) and (B, A) are different.
    3. Halve the product so each handshake is counted once.
    4. Return the result.

    The solution in Go

    func countHandShakes(n int) int {
    return (n * (n - 1)) / 2
}

    Why is integer division safe here? Among two consecutive integers, n and n - 1, one is always even, so the product is always even. Dividing by 2 leaves no remainder, and Go's integer division, which cuts off any fraction, loses nothing.

    The order of operations also matters. Multiplying first and dividing afterwards is exact. Halving one factor first would be wrong for odd n when using integers: n / 2 * (n - 1) with n = 3 gives 1 * 2 = 2 instead of 3.

    Complexity

    The function does a fixed number of arithmetic operations, so it runs in O(1) time and uses O(1) space. The loop-based count would take O(n²) time, or O(n) if you added up the numbers 1 to n - 1 one by one.

    Edge cases and common mistakes

    • One friend. n = 1 gives 1 * 0 / 2 = 0. Nobody to shake hands with.
    • Zero friends. n = 0 gives 0 * (-1) / 2 = 0. The result is still correct, although the intermediate product uses a negative number.
    • Two friends. One handshake: 2 * 1 / 2 = 1.
    • Forgetting the division. n * (n - 1) is twice the correct answer.
    • Using n * n / 2. That includes people shaking their own hand, and it is wrong.
    • Very large n. An int has 64 bits in Go, and overflow wraps silently, so for an enormous n the product n * (n - 1) could wrap before the division. That is far beyond what a group of friends needs.

    Small inputs to try: countHandShakes(3) gives 3, countHandShakes(4) gives 6, countHandShakes(2) gives 1 and countHandShakes(1) gives 0.

    Keep going with GoAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free