HackerRank: Handshake

Time to shake hands with a lot of people in the next HackerRank challenge called Handshake. The problem reads

At the annual meeting of Board of Directors of Acme Inc, every one starts shaking hands with everyone else in the room. Given the fact that any two persons shake hand exactly once, Can you tell the total count of handshakes?

Input Format
The first line contains the number of test cases T, T lines follow.
Each line then contains an integer N, the total number of Board of Directors of Acme.

Output Format

Print the number of handshakes for each test-case in a new line.

Arrive one person at a time

Let us assume that the directors arrive one at a time. In order to ensure that everyone shakes hand with everyone once, every time a new person arrives he will shake hands with everyone already arrived. Then everyone has shaken hands with everyone else at all times.

For the first person to arrive, he will have to shake hands with 0 people.

The second person to arrive, she will have to shake hands with 1 person.

Upon arrivalĀ  of the third person, she will have to shake hands with 2 people.

You see where this goes. The nth person to arrive will have to shake hands with n-1 people.

In order to get the total amount of handshakes we then have to sum up all the people when they arrive. We can do that as

where h is the number of handshakes and n is the number of people

Arithmetic sequence of handshakes

Currently we have a formula that we could implement in O(n) which means that for every result we want, we need to do the actual sum over all the numbers. Gauss discovered that in general summing consecutive integers can be written as the general formula as

Which means we can reduce the complexity to O(1). However, as we don’t want to sum 1,2,…n but only to n-1. The formula looks like

 

Implementing this in python can be done as

def handshake(n):
    return ((n - 1) * n) // 2

Notice that I have used the integer division in python. This is only done to ensure that we return the result as an integer. I could also have converted it all to integer afterwards.

Posted by Kristian

3 comments

Jean-Marie Hachey

Hi Kristian !

Line 2 in your code: typo ? :
// instead of /

Application of Python with n = 100

Python 3.6.1 (v3.6.1:69c0db5, Mar 21 2017, 17:54:52) [MSC v.1900 32 bit (Intel)] on win32
Type “help”, “copyright”, “credits” or “license” for more information.

(100-1)*100/2
4950.0

No I meant to write // which will do integer division instead of floating point.

Jean-Marie Hachey

Thank you Kristian

Python 3.6.1 (v3.6.1:69c0db5, Mar 21 2017, 17:54:52) [MSC v.1900 32 bit (Intel)] on win32
Type “help”, “copyright”, “credits” or “license” for more information.

(100-1)*100 // 2
4950

Leave a Reply