Start learning free

LESSON 55 OF 414 · CALCULATIONS - CHALLENGES

Hand Shakes in Rust: Counting Pairs with n(n-1)/2

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

    RUST · CALCULATIONS - CHALLENGES

    Hand Shakes in Rust, explained

    Problem overview

    A group has n friends, and when they meet, everybody shakes hands with everybody else once. The function count_hand_shakes 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.

    Approach

    You could simulate it: for each person, count the handshakes with the people who come after them, and add everything up. That works, but it needs a loop. A formula is shorter and faster.

    Counting from one person's side

    Each of the n people shakes hands with the other n - 1 people, which gives n * (n - 1) handshakes. But every handshake was counted twice: once from each of the two people involved. With three friends, the product is 3 * 2 = 6, and each of the three real handshakes shows up twice. Dividing by 2 corrects it.

    The answer is n * (n - 1) / 2.

    Counting a different way

    Write out the handshakes for four friends, A to D, grouped by the first person:

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

    A starts 3 handshakes, B starts 2, C starts 1 and D starts none, for 3 + 2 + 1 = 6. Arranged as rows of dots this forms a staircase. Two copies of a staircase fit together into a rectangle with n - 1 rows and n columns, so the staircase holds half of (n - 1) * n. It is the same formula, and for n = 4 it gives 4 * 3 / 2 = 6.

    Step by step

    1. Multiply n by n - 1. This counts each handshake from both sides.
    2. Divide by 2 to count each handshake only once.
    3. Return the result.

    The division is exact. Of any two consecutive numbers, n and n - 1, one is even, so their product is even and halving it leaves no remainder. That matters in Rust, where dividing two integers drops the fractional part.

    The solution in Rust

    impl Solution {
    fn count_hand_shakes(n: i32) -> i32 {
        return (n * (n - 1)) / 2;
    }
}

    The parentheses around n * (n - 1) are not required, since * and / have equal precedence and run left to right, but they make the intention clear. The division happens last, after the multiplication, which is what the formula needs: dividing n by 2 first would lose a fraction whenever n is odd.

    Rust details

    • Integer division. With i32 operands, / gives an i32. Here the product is always even, so nothing is lost.
    • Return. The line could also be written as the final expression (n * (n - 1)) / 2, without return and without a semicolon.

    Complexity

    The function does one subtraction, one multiplication and one division regardless of n, so it takes O(1) time and O(1) space. A loop that adds up 1 + 2 + ... + (n - 1) would take O(n) time.

    Edge cases and common mistakes

    • One friend, or none. With n = 1 the formula gives 1 * 0 / 2 = 0, which is right: nobody to shake hands with. For n = 0 it computes 0 * (-1) / 2, which is also 0.
    • Two friends. One handshake: 2 * 1 / 2 = 1.
    • Forgetting to halve. n * (n - 1) alone counts every handshake twice. For n = 3 it returns 6 instead of 3.
    • Using n * n. That counts each person shaking hands with themselves as well.
    • Overflow. The product is computed before the division, in i32. For n = 46341 the product still fits and the function returns 1073720970. For n = 46342 the product goes past the i32 limit, and in the optimized builds the lessons use it wraps silently, so the function returns -1073716337 instead of the true count, even though the true count itself fits in an i32. In a debug build the multiplication would panic instead. Normal test sizes stay below this limit.

    Testing

    • count_hand_shakes(3) returns 3.
    • count_hand_shakes(4) returns 6.
    • count_hand_shakes(10) returns 45.
    • count_hand_shakes(1) returns 0.
    Keep going with RustAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free