Start learning free

LESSON 52 OF 415 · CALCULATIONS - CHALLENGES

Hand Shakes in Swift: 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 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

    SWIFT · CALCULATIONS - CHALLENGES

    Hand Shakes in Swift, explained

    Problem overview

    The method countHandShakes receives n, the number of friends in a group. Everybody shakes hands with everybody else exactly once, and the method 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 there are six: (A, B), (A, C), (A, D), (B, C), (B, D) and (C, D).

    Approach

    One way is to count by hand: A shakes with the 3 others, B then adds 2 new ones, C adds 1, and D adds none. The total is 3 + 2 + 1 = 6. In general the sum is (n - 1) + (n - 2) + ... + 1. A loop could add it up, but a formula is shorter and faster.

    There is a quicker way to see the formula. Each of the n people shakes hands with the other n - 1 people, which makes n * (n - 1). But that counts every handshake twice, once from each side: A's handshake with B is also B's handshake with A. Dividing by 2 fixes this:

    handshakes = n * (n - 1) / 2

    For n = 4 that is 4 * 3 / 2 = 6, which matches the list.

    Step by step

    1. Count the ordered pairs. Multiply n by n - 1. Wrap n - 1 in parentheses so the subtraction happens first.
    2. Remove the double counting. Divide the product by 2.
    3. Return the result. The method returns an Int, which is what the division of two integers gives.

    The solution in Swift

    class Solution {
    func countHandShakes(_ n: Int) -> Int {
        return (n * (n - 1)) / 2
    }
}

    Swift details worth knowing:

    • The division is exact. Of any two consecutive numbers, one is even, so n * (n - 1) is always even. Integer division, which drops fractions, therefore loses nothing here.
    • Multiply before dividing. Doing the multiplication first keeps every step a whole number. Swift evaluates * and / from left to right anyway.
    • Overflow crashes. Int is 64 bits, and arithmetic that overflows stops the program at run time. The product n * (n - 1) only gets that large once n passes about 3.04 billion, far beyond what a group of friends needs.

    Another way to see the formula

    Write the handshakes of the friend who joins last. When person number k arrives, they shake hands with the k - 1 people already there. So the total for n people is 0 + 1 + 2 + ... + (n - 1). Pairing the first term with the last, the second with the second to last, and so on, gives pairs that each add up to n - 1. There are n / 2 such pairs, which leads to the same n * (n - 1) / 2.

    Complexity

    Time and space are both O(1): the method does one subtraction, one multiplication and one division, whatever the value of n. A loop that adds 1 + 2 + ... + (n - 1) would take O(n) time.

    Edge cases and common mistakes

    • One person or nobody. For n = 1 the formula gives 1 * 0 / 2 = 0, and for n = 0 it also gives 0. No pair, no handshake.
    • Two people. 2 * 1 / 2 = 1: a single handshake.
    • Forgetting to halve. n * (n - 1) counts each handshake twice.
    • Using n * n / 2. That includes people shaking their own hands.
    • Missing parentheses around n - 1. n * n - 1 is a different number.

    Testing

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