- Practice
- Mathematics
- Fundamentals
- Handshake
- Discussions

# Handshake

# Handshake

DocFarren + 0 comments Try this reasoning:

I (PersonA) am one out of N people, so I need to shake hands with (N-1) people. This reasoning holds true for all of the N people, so the number of hand shakes is N * (N-1). Now that PersonA and PersonB shook hands, PersonB and PersonA (same people, but from PersonB's perspective) don't need to shake anymore. So we initially counted each combination twice. Therefore, the number of hand shakes is

nShakes = (N * (N-1)) / 2

PPMBrouwers + 1 comment In an example of 4 people: The first person can shake hands with all the others (N-1)=3. The seconds person can shake hands with all the others, without 1: (N-1-1)=2, third = (N-1-1-1)=1, fourth = (N-1-1-1-1)=0. Hence we get exactly range(4) [at least in Python]. So if we do

sum(range(N))

0+1+2+3 == 6, we get the total number of handshakes.

stephen_berks056 + 0 comments That's brief, but it runs in linear time. You can do it in constant time with (N-1) * N // 2.

afando + 1 comment It is a standard combinatorics problem. You need to select a pair of people from N people. How many different pairs are there? N choose 2. N! / ((N-2)! * 2!) which simplifies to (N * (N-1)) / 2.

amani_kilumanga + 1 comment I believe one of your exclamation points is misplaced.

N! / (R!(N - R)!) = N! / (2!(N - 2)!)

afando + 0 comments Thanks, edited!

UriyaBA + 1 comment def handshake(n): return sum(range(n))

Once you understand the logic it's amazing how short the solution is.

hoang_pham + 0 comments Nice solution!

alayek + 1 comment I have a qualm with the sample test cases provided. Don't use 0 or 1, because most of the times they represent some boundary case or special case.

Maybe you can include one example with a bigger number, like 4 or 5?

aryaman_arora201 + 0 comments If you use the most efficient solution, 0 and 1 are not boundary cases (hint hint)

jasbir_singh252 + 0 comments why it is running succefully for n-1 ?

rajeevpodar + 0 comments Smallest Code written in HackerRank so far:

`return ((n-1)*n) /2;`

zac_c_petit + 2 comments You can generalize this using Binomial Coefficients https://en.wikipedia.org/wiki/Binomial_coefficient

saads + 2 comments That only works for

small numbers because of the factorials.*very*zac_c_petit + 1 comment [deleted]saads + 0 comments Oh, what formula did you use? I used the factorial formula.

zac_c_petit + 0 comments No idea what you mean. This approached worked fine in my C# submission for 0 < N < 10^6 with each result in 20ms or less.

aryaman_arora201 + 0 comments

asbear + 2 comments This is adding from 1 to P-1 when P is number of person. so if you just use ((P-1)+1)*(P-1)/2 when P > 1 and 0 when P = 1 it will work.

Darmen + 2 comments it's formula easiest ((p - 1) * p / 2)

EvilCartman + 2 comments some how i've ended with

**(P * P - P) / 2**formula ;)developeransh + 1 comment can u solve this withouth formula..as i have another trick to do it withouth formula

asbear + 2 comments it's not difficult even without the formula but the complexity would be too bad. what's the complexity of yours?

EvilCartman + 0 comments It's

**O(nÂ²)**, god's sake...trendsetter37 + 1 comment You can do it in

**O(n)**def hs(num): total = 0 for i in range(num, 0, -1): total += i-1 return total

Am I right?

teffuben + 0 comments Yes you can. You are right, but it is better to have a simple formula to calculate it for you to avoid complexity, and to improve your math thinking skills.

I also did it in a similar manner to you, but thought it better to look for a formula.

swhitlock410 + 0 comments @EvilCartman, you are still correct.

(P * (P - 1))/2 = (P * P - P)/ 2 = (P^2 - P) /2

^ is my way of representing exponents.

asbear + 0 comments haha that's correct. I just left (P-1) as is to help others understanding simpler. :)

Kiuru + 4 comments This probably soudns like a stupid question to you but how do you figure out such formulas? I solved this with a loop which is fine if the numbers aren't too big. In school I was neither very good nor very bad at maths. Is there some kind of "strategy" to find them?

AffineStructure + 0 comments [deleted]ChristopheB + 0 comments The strategy that I used was that I visualized the problem as a square grid in which both the columns and rows represent the different persons. It is assumed that a person does not shake hands with him or herself so that means the diagonal is empty. If person 1 shakes hands with person 2, I can place a mark on the first row, second column. If person 2 shakes hands with person 3 I place a mark on the second row, third colummn and so on. In the end you will see that you have marked all elements of the grid above the diagonal.

Unfortunately, I think that at this point you do need some background in mathematics to quickly see that there is a formula that will give you the number of these elements. If not, you can always try to get the solution for small numbers of N and hopefully discover a relationship before N gets too big :)

mahiruinamichan + 0 comments It's arithmetic progression with d = 1. https://en.wikipedia.org/wiki/Arithmetic_progression

harishshet222 + 0 comments int handshake(int n) { int sum =0; for(int i=1;i<n;i++) { sum+=(n-i); } return sum; }

Sort 114 Discussions, By:

Please Login in order to post a comment