Recursion: Handshake problem

Coding Interview Questions

1 min read

Problem Statement:

You are given a number N, that will represents number of people at the party.
You need to find the total number of handshake such that a person can handshake only once.

Example:

Input: 5

Output: 10

Solution Explanation:

We can solve this problem by using recursion.

The nth person has n-1 choices to shake hands, and chooses one person.

Similarly, the solution will now reduce to n-1, same recursion can be applied.

So we can use: count_handshake(n) = (n-1) + handshake(n-1)

Base case will be, if n == 0, return 0.

Time Complexity: O(1)
Space Complexity: O(1)

Code Solution

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

int solution(int n) { return n * (n - 1) / 2; }

int main()
{
    int n = 5;
    cout << solution(n) << endl;
    return 0;
}