Start learning free

LESSON 53 OF 410 · CALCULATIONS - CHALLENGES

Hand Shakes in Python: Counting Handshakes with a Formula

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 starts 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

    PYTHON · CALCULATIONS - CHALLENGES

    Hand Shakes in Python, explained

    Problem overview

    The method countHandShakes(self, n) receives the number of friends n in a group. Everybody shakes hands with everybody else exactly once, and the method returns how many handshakes happen in total.

    For n = 3 the friends are A, B and C, and the handshakes are (A, B), (A, C) and (B, C). The answer is 3. Order inside a pair does not matter: A shaking B's hand and B shaking A's hand is one handshake, not two.

    Approach: count pairs, not handshakes one by one

    A handshake is a pair of two different people, so the question is how many pairs you can form from n people. Listing them for n = 4 gives six:

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

    Person A has 3 handshakes that start with A, B adds 2 more that are new, and C adds 1. The total is 3 + 2 + 1 = 6. In general the answer is (n - 1) + (n - 2) + ... + 1, the sum of the numbers from 1 to n - 1.

    You could add these up in a loop, which takes O(n) time. A short argument gives a closed formula instead. Each of the n people shakes hands with the other n - 1 people. That counts every handshake twice, once from each side, so the number of distinct handshakes is half of n * (n - 1).

    The same count appears in a picture. Write the first person of each handshake in a grid with n - 1 rows and n columns. Exactly half of the cells are filled, so the answer is the area divided by 2.

    Step by step

    The lesson has a single step, and it is the whole solution:

    1. Compute n * (n - 1). This is the number of ordered pairs: person X shaking hands with person Y, counted separately from Y with X.
    2. Halve it with //. Every handshake was counted twice, so the division removes the duplicates. The product n * (n - 1) is always even, because one of two consecutive numbers is even, so the division leaves no remainder.
    3. Return the result.

    The solution in Python

    class Solution:
    def countHandShakes(self, n: int) -> int:
        return (n * (n - 1)) // 2

    Why // and not /? In Python, / always returns a float, even when the division is exact: 6 / 2 is 3.0, while 6 // 2 is 3. The method promises an int, so use //.

    The float result has a second drawback. A float holds only about 15 to 17 significant digits, so for very large n the product would be rounded before the division. Python's int has no size limit, so // stays exact: countHandShakes(10**20) returns 4999999999999999999950000000000000000000, which is the exact value.

    Complexity

    • Time: O(1). The method does one multiplication, one subtraction and one division, whatever n is. (For huge numbers the arithmetic itself takes longer, but for any ordinary input it is constant.)
    • Space: O(1). No extra data is stored.

    A loop that adds 1 + 2 + ... + (n - 1) gives the same answer in O(n) time, which is fine for a small group but wasteful when a formula exists.

    Edge cases and common mistakes

    • One person or nobody. n = 1 gives 1 * 0 // 2 = 0 and n = 0 gives 0 * (-1) // 2 = 0. Nobody to shake hands with means no handshakes, and the formula handles it with no special case.
    • Using n * n / 2. That counts each person shaking their own hand. The n - 1 removes it.
    • Forgetting to halve. n * (n - 1) counts both directions, so for n = 3 it gives 6, not 3.
    • Using / instead of //. The number is right but the type is wrong: 3.0 instead of 3.

    Testing

    For n from 0 to 7 the answers are 0, 0, 1, 3, 6, 10, 15 and 21. Each step adds one more than the last, because the new person shakes hands with everyone already present. With n = 4 the six pairs listed above match the formula: 4 * 3 // 2 = 6.

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