Start learning free

LESSON 56 OF 348 · CALCULATIONS - CHALLENGES

Hand Shakes in TypeScript: Counting Pairs 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 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

    TYPESCRIPT · CALCULATIONS - CHALLENGES

    Hand Shakes in TypeScript, explained

    Problem overview

    The method countHandShakes receives n, the number of friends in a group, and returns how many handshakes happen when everybody shakes hands with everybody else. Each pair of friends shakes hands once.

    With n = 3 and friends A, B and C, the handshakes are (A, B), (A, C) and (B, C), so the answer is 3. With four friends A, B, C and D there are six: (A, B), (A, C), (A, D), (B, C), (B, D) and (C, D).

    Approach: count pairs, not people

    You could simulate the meeting with two nested loops, one handshake at a time. That works, but it takes time proportional to n squared, and the pattern behind it gives a direct formula.

    List the handshakes by who starts them. For four friends, A shakes hands with 3 others (B, C, D). B has already shaken A's hand, so B adds 2 more. C adds 1, and D adds none. The total is 3 + 2 + 1 = 6. In general the answer is (n - 1) + (n - 2) + ... + 1.

    There is a shorter way to see the same sum. Every one of the n people shakes hands with the other n - 1 people, which makes n * (n - 1) handshakes if you count from each person's side. But each handshake involves two people, so it was counted twice, once from each side. Halving gives the number of distinct handshakes:

    n * (n - 1) / 2

    For n = 4 that is 4 * 3 / 2 = 6, and for n = 3 it is 3 * 2 / 2 = 3.

    Step by step

    1. Take the number of people who can be shaken hands with. Each person has n - 1 possible partners, since nobody shakes their own hand.
    2. Multiply by the number of people. n * (n - 1) counts every handshake from both sides.
    3. Divide by 2 so that each handshake counts once.
    4. Return the result. The method needs a single return statement.

    The solution in TypeScript

    class Solution {
    countHandShakes(n: number): number {
        return (n * (n - 1)) / 2;
    }
}

    Some details worth knowing:

    • The division is safe. In TypeScript, / on numbers keeps the fraction (7 / 2 is 3.5), so you might expect to need Math.floor. Here you don't, because of a fact about whole numbers: n and n - 1 are consecutive, so one of them is even, and their product is always even. Dividing by 2 leaves no remainder.
    • Types are erased. The annotation n: number documents the intent and lets the compiler check callers, but it does nothing at run time. If a caller gets around the type checker and passes a non-integer such as 3.5, the method returns 4.375 instead of failing.
    • One number type. Every TypeScript number is a double, so there is no integer overflow. The product n * (n - 1) is exact as long as it stays below 2^53, which holds for roughly 94 million friends or fewer.
    • Methods on a class. The lesson wraps the logic in a Solution class. The method is called on an instance, as in new Solution().countHandShakes(4).

    Complexity

    Time: O(1). The method does one multiplication, one subtraction and one division, no matter how large n is.

    Space: O(1). It stores no extra data.

    Edge cases and common mistakes

    • Forgetting to halve. n * (n - 1) gives 12 for four friends instead of 6.
    • Using n * n / 2. That counts handshakes with yourself as well. For n = 4 it gives 8.
    • Precedence. Writing n * n - 1 / 2 divides only the 1. Keep the parentheses around n - 1.
    • One person or none. n = 1 gives 0, which is right: nobody to shake hands with. n = 0 also returns zero, though JavaScript prints it as -0, because 0 * -1 is negative zero. It still compares equal to 0 with ===.
    • Two people. n = 2 gives exactly 1 handshake.

    Testing

    • n = 2 gives 1.
    • n = 3 gives 3.
    • n = 4 gives 6.
    • n = 10 gives 45.
    • n = 100000 gives 4999950000.
    Keep going with TypeScriptAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free