Number of handshakes, each person only shakes hands once

Suppose you are at a social gathering. If you only shake hands once, can you calculate how many handshakes you can do? This question may amuse you. This problem can be solved by using mathematical methods of permutation and combination. However, mathematical operations can be time consuming.

In this article, we will discuss how to solve this problem using C. We'll explore different approaches, including mathematical formulas, recursion, and other combinatorial techniques.

Input and output scenarios

Suppose you have N number of people in a gathering. You want to calculate the number of handshakes possible such that a person shakes hands only once.

Input: N = 16
Output: 120
Input: N = 11
Output: 55

Using the Formula for Handshakes

The formula for finding the number of handshakes in a gathering of N people is −

No. of handshakes = N *(N-1) /2

Each of the N people will shake the hands with (N-1) individuals (excluding the person itself) and the handshakes between two individuals is not counted twice.

For Example, if the number of individuals is 14. Then, number of handshakes are

Handshakes = 14 * (14 - 1)/ 2
           = 14 * 13 / 2
           = 182/2
           = 91

Example

In the example below, we are using the formula to calculate the number of handshakes. Here we simply use mathematical operators, taking as input the number of people at the party.

#include <iostream>
using namespace std;

int count(int N) {
   // Formula: N * (N-1) / 2
   return (N * (N - 1)) / 2;
}

int main() {
   int totalIndividuals= 10;
   int numHandshakes = count(totalIndividuals);
   std::cout << "Number of handshakes: " << numHandshakes << std::endl;
   return 0;
}

Output

Number of handshakes: 45

Use for loop

Here, we count the number of handshakes by iterating from 1 to ‘N-1’ and adding all the values.

Example

#include <iostream>
using namespace std;

int count(int N) {
   int numHandshakes = 0;

   for (int x = 1; x < N; x++) {
      numHandshakes += x;
   }

   return numHandshakes;
}

int main() {
   int totalIndividuals = 10;
   int numHandshakes = count(totalIndividuals);
   std::cout << "Number of handshakes: " << numHandshakes << std::endl;
   return 0;
}

Output

Number of handshakes: 45

Use recursion

We can use recursion for calculating the number of handshakes. By doing so, we divide the problem into smaller problems by considering one person at a time.

Example

#include <iostream>
using namespace std;

int count(int N) {
   if (N <= 1)
      return 0;
   return (N - 1) + count(N - 1);
}

int main() {
   int totalIndividuals = 20;
   int numHandshakes = count(totalIndividuals);
   std::cout << "Number of handshakes: " << numHandshakes << std::endl;
   return 0;
}

Output

Number of handshakes: 190

Using While Loop

Here, we use a while loop with a decrementing counter to count the number of handshakes. The loop starts with the total number of people and then decrements the counter one by one after each iteration.

Example

#include <iostream>
using namespace std;

int count(int N) {
   int numHandshakes = 0;

   while (N > 1) {
      numHandshakes += N - 1;
      N--;
   }

   return numHandshakes;
}

int main() {
   int totalIndividuals = 16;
   int numHandshakes = count(totalIndividuals);
   std::cout << "Number of handshakes: " << numHandshakes << std::endl;
   return 0;
}

Output

Number of handshakes: 120

Use dynamic programming

Here, we have used dynamic programming for the calculation.

• Initialize a ‘dp’ vector to store the number of handshakes.

• Iterate from 1 to N. In each iteration, it declares the number of handshakes as the sum of previous handshakes and the present number of individual minus 1.

Example

#include <iostream>
#include <vector>
using namespace std;

int count(int N) {
   std::vector<int> dp(N + 1);
   dp[0] = 0;

   for (int x = 1; x <= N; x++) {
      dp[x] = dp[x - 1] + (x - 1);
   }

   return dp[N];
}

int main() {
   int totalIndividuals = 21;
   int numHandshakes = count(totalIndividuals);
   std::cout << "Number of handshakes: " << numHandshakes << std::endl;
   return 0;
}

Output

Number of handshakes: 210

Note − This method helps avoid redundant calculations. Here we store the previously calculated value in the "dp" vector, which you can access and reuse anytime. This makes the algorithm efficient and reduces overall computation time.

Conclusion

We've discussed various ways to count the number of handshakes a person has to make only once. These methods include using mathematical operators for formula calculations, using for loops, recursion, while loops, and dynamic programming. Each method has its advantages. Dynamic programming is a more systematic and organized approach to problem solving. Depending on your specific requirements, you can use either method.

The above is the detailed content of Number of handshakes, each person only shakes hands once. For more information, please follow other related articles on the PHP Chinese website!