- Practice
- Mathematics
- Fundamentals
- Handshake
- Discussions

# Handshake

- RK
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.

- SB
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.

- AF
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)!)

- AF
afando + 0 comments Thanks, edited!

- A
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?

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

Shadow_3115 + 1 comment int main(){ int T; cin >> T; for(int a0 = 0; a0 < T; a0++){ int N; cin >> N; int x=N*N/2; int y=N/2; cout<<(x-y)<<"\n"; } return 0; }

- VS
vikramsaraf3000 + 1 comment if you change to this then it will become shorter

int x=(N-1)*N/2; cout<<(x)<<"\n";

- J
jeetendra_sobre + 0 comments what about N=1?

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

- SS
saads + 2 comments That only works for

small numbers because of the factorials.*very*zac_c_petit + 1 comment [deleted]- SS
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.

- A
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.

- DZ
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 + 0 comments 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?

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. :)

- N
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]- CB
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

- MP
modyali_fox + 0 comments return n / 2;

- D
www_dbasak + 0 comments # include

# include

using namespace std; int main() { long long int t,n,a; cin>>t; while(t--) { cin>>n; a=n/2; cout<

}

this code gave the wrong answer in test case 11. how can i fix this?

Sowdha + 0 comments Why does "Floating Point Exception" happen when I submit the code? (It gets across the testcase 0)

Sort 92 Discussions, By:

Please Login in order to post a comment