Start learning free

LESSON 52 OF 414 · CALCULATIONS - CHALLENGES

Hand Shakes in Scala: A Closed-Form 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

    SCALA · CALCULATIONS - CHALLENGES

    Hand Shakes in Scala, explained

    Problem overview

    There are n friends, and everyone shakes hands with everyone else exactly once. The method countHandShakes returns how many handshakes happen.

    For n = 3 with friends A, B and C, the handshakes are (A, B), (A, C) and (B, C), so the answer is 3. For n = 4 the pairs are (A, B), (A, C), (A, D), (B, C), (B, D) and (C, D), which makes 6.

    Approach

    Counting by listing pairs works for small groups, but a formula is better. There are two ways to reach it.

    Count from each person's side

    Each of the n people shakes hands with the other n - 1 people. That gives n * (n - 1). But a handshake involves two people, so it was counted once from each side. Dividing by 2 fixes the double counting: n * (n - 1) / 2. For n = 4 that is 4 * 3 / 2 = 6.

    Add up the pairs by first friend

    A shakes hands with 3 others (B, C, D), B has 2 new ones (C, D), and C has 1 (D). The total is 3 + 2 + 1 = 6. In general the sum is (n - 1) + (n - 2) + ... + 1. Write that sum once forwards and once backwards, one above the other. Each of the n - 1 columns adds up to n, so the two rows together total n * (n - 1), and the sum itself is half of that: the same formula.

    A loop that adds up the sums would run in O(n) time. The formula needs a single multiplication, subtraction and division.

    Step by step

    1. Compute n - 1. This is how many other people each person meets.
    2. Multiply by n. This counts every handshake twice.
    3. Divide by 2. The product is always even, since either n or n - 1 is even. Integer division therefore loses nothing.
    4. Return the result.

    The solution in Scala

    class Solution {
    def countHandShakes(n: Int): Int = {
        return (n * (n - 1)) / 2
    }
}

    Scala details:

    • The multiplication happens first. The parentheses make the order explicit. Writing n * (n - 1) / 2 would evaluate the same way, because * and / have equal precedence and group left to right. Dividing n - 1 by 2 first and then multiplying would be wrong: for n = 4 it would compute 4 * (3 / 2) = 4.
    • Integer division. Both sides are Int, so the result is an Int with any remainder dropped. Since the product is even, there is no remainder to drop.
    • return is optional. The last expression is the block's value, so the line could be written without it.

    Complexity

    Time: O(1). A fixed number of arithmetic operations.

    Space: O(1). No extra storage.

    Edge cases and common mistakes

    • Zero or one friend. countHandShakes(1) is 0, since the one person has nobody to meet. countHandShakes(0) is 0 as well.
    • Forgetting to halve. n * (n - 1) counts each handshake twice. For n = 3 it gives 6 instead of 3.
    • Using n * n / 2. That counts a person shaking their own hand. For n = 3 it gives 4 instead of 3.
    • Overflow. An Int wraps silently past 2,147,483,647, and the intermediate product n * (n - 1) is twice the answer. For n = 100000 the true answer is 4,999,950,000, which doesn't fit in an Int, and the method returns 704982704. With a Long parameter and result type, the same formula would stay exact for much larger groups.

    Testing

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