Start learning free

LESSON 52 OF 348 · CALCULATIONS - CHALLENGES

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

    KOTLIN · CALCULATIONS - CHALLENGES

    Hand Shakes in Kotlin, explained

    Problem overview

    A group of n friends meets, and everybody shakes hands with everybody else, once per pair. The function countHandShakes must return how many handshakes that makes.

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

    Approach

    You could list all the pairs and count them, but a formula is shorter. There are two ways to reach it.

    Counting from each person

    Each of the n people shakes hands with the other n - 1 people, so n * (n - 1) counts every handshake. But that counts each one twice: the handshake (A, B) is counted once from A's side and once from B's side. Dividing by 2 fixes that:

    handshakes = n * (n - 1) / 2

    Adding up what's left

    Another way to see it is to go through the people in order. A shakes hands with n - 1 others, B with n - 2 others not yet counted, and so on, down to 1 for the second to last person and 0 for the last. For n = 4 that is 3 + 2 + 1 = 6. Laid out as a grid of n - 1 rows and n columns, the handshakes fill exactly half of the cells, so the count is the grid's area divided by two, (n - 1) * n / 2. It's the same formula.

    The formula involves no loop, so the answer comes in constant time however large n is.

    Step by step

    1. Multiply n by n - 1. This counts every ordered pair of different people: who shakes with whom, with the direction included.
    2. Divide by 2. This merges the two directions of each handshake into one.
    3. Return the result.

    The division never loses anything. Of two consecutive numbers, n and n - 1, one is always even, so their product is even and halves exactly. Kotlin's integer division, which drops the remainder, therefore returns the exact count.

    The solution in Kotlin

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

    Kotlin details to be aware of:

    • Order of operations. The product is computed first and then divided. The parentheses around n * (n - 1) are not required, since * and / run left to right, but they make the intent clear.
    • Integer division. With Int operands, / returns an Int. Because the product is always even, nothing is truncated here.
    • Division first would be wrong. Writing n / 2 * (n - 1) truncates before multiplying: for n = 3 it computes 1 * 2 = 2, not 3.

    Complexity

    The function does a fixed number of arithmetic operations, so time is O(1) and extra space is O(1). Counting the pairs one by one with nested loops would take O(n²) time.

    Edge cases and common mistakes

    • One person or nobody. With n = 1 the formula gives 0, because there is nobody to shake hands with. With n = 0 it also gives 0, because the product is 0.
    • Two people. n = 2 gives 2 * 1 / 2 = 1: one handshake.
    • Forgetting to halve. n * (n - 1) alone gives 6 for n = 3 instead of 3.
    • Overflow. An Int in Kotlin is 32 bits, and arithmetic that goes past its range wraps around silently. The product n * (n - 1) exceeds 2147483647 once n reaches 46342, even though the true answer would still fit. For n = 100000 this function returns 704982704, while the real count is 4999950000. A solution for such inputs would compute with Long. This lesson's signature uses Int, so keep that, and stay aware of the limit.

    Testing

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