Start learning free

LESSON 51 OF 347 · CALCULATIONS - CHALLENGES

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

    C# · CALCULATIONS - CHALLENGES

    Hand Shakes in C#, explained

    Problem overview

    There are n friends, and everybody shakes hands with everybody else exactly once. CountHandShakes must return the total number of handshakes.

    For three friends A, B and C, the handshakes are (A, B), (A, C) and (B, C). That is 3. For four friends A, B, C and D there are six: (A, B), (A, C), (A, D), (B, C), (B, D) and (C, D).

    Approach

    The problem is to count the pairs of people. You could list every pair, but a formula is simpler.

    Counting from each person

    Each of the n people shakes hands with the other n - 1 people. Multiplying gives n * (n - 1). But this counts each handshake twice: the handshake (A, B) is counted once for A and once for B. So divide by 2.

    The same idea with a staircase

    Another way to reach it is to list the handshakes by their first person. For four friends, A has 3 handshakes (with B, C, D), B has 2 more (with C, D), C has 1 more (with D), and D has none new. The total is 3 + 2 + 1 = 6. Written as a rectangle of n - 1 rows and n columns, the handshakes fill exactly half of it, which gives the area (n - 1) * n divided by 2. Both ways lead to the same formula.

    Check it with n = 4: 4 * 3 / 2 = 6. With n = 3: 3 * 2 / 2 = 3.

    Step by step

    1. Compute n * (n - 1). This is the number of ordered pairs, counting both (A, B) and (B, A).
    2. Divide by 2 to count each unordered pair once.
    3. Return the result.

    The division by 2 is always exact. Of two consecutive numbers n and n - 1, one is even, so their product is even. That matters in C#, where dividing two int values truncates the fraction. Here nothing is lost, so the integer division gives the exact answer.

    The solution in C#

    class Solution {
    public int CountHandShakes(int n) {
        return (n * (n - 1)) / 2;
    }
}

    Details to know:

    • The multiplication happens before the division, because the parentheses say so. The order matters: n * ((n - 1) / 2) would truncate (n - 1) / 2 first and give a wrong answer for even n. For n = 4 it would compute 4 * 1, which is 4 instead of 6.
    • All values are int, so the division is an integer division and the result is an int.
    • int arithmetic does not report overflow by default. See the edge cases below.

    Complexity

    The method does a fixed amount of arithmetic, so time is O(1) and extra space is O(1). A loop that adds (n - 1) + (n - 2) + ... + 1 would take O(n) time to get the same number, so the formula is both shorter and faster.

    Edge cases and common mistakes

    • One friend or none. CountHandShakes(1) is 1 * 0 / 2 = 0, and CountHandShakes(0) is also 0. Nobody to shake hands with, so zero is right.
    • Two friends. 2 * 1 / 2 = 1, a single handshake.
    • Overflow for large n. The product n * (n - 1) is computed as an int before the division. Once it passes 2,147,483,647, which happens for n above 46,341, it wraps around silently and the answer is wrong. For example, CountHandShakes(100000) gives 704982704 instead of the true 4,999,950,000, which doesn't fit in an int anyway. If you needed large n, you would use long for the parameter and return type.
    • Forgetting to halve. Returning n * (n - 1) counts every handshake twice.
    • Using n * n / 2. That counts a person shaking their own hand.

    Testing

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