Hand Shakes - Time Complexity: O(1) - C++ Solution

## Understanding the Problem In this problem, we are given `n` friends in a group. When they meet, everybody shakes hands with everybody else. We need to determine the total number of handshakes that occur. ### Input and Output Formats - **Input**: An integer `n` representing the number of friends. - **Output**: An integer representing the total number of handshakes. ### Constraints and Assumptions - `1 <= n <= 10^9` - Each friend shakes hands with every other friend exactly once. ### Example **Input**: `n = 3` **Output**: `3` **Explanation**: Considering A, B, and C are the 3 friends. The handshakes are: (A, B), (A, C), and (B, C). ## Core Challenge The core challenge is to determine the number of unique pairs that can be formed from `n` friends. This is a classic combinatorial problem where we need to find the number of ways to choose 2 items from `n` items, which is given by the combination formula `C(n, 2)`. ## Approach ### Naive Solution A naive approach would be to iterate through each pair of friends and count the handshakes. However, this approach is not optimal as it has a time complexity of O(n^2), which is infeasible for large values of `n`. ### Optimized Solution The optimized solution leverages the combinatorial formula for combinations. The number of ways to choose 2 items from `n` items is given by: \[ C(n, 2) = \frac{n \times (n - 1)}{2} \] This formula directly gives us the number of handshakes without the need for iteration, resulting in a time complexity of O(1). ### Derivation 1. Each friend shakes hands with every other friend exactly once. 2. For `n` friends, the number of unique pairs (handshakes) is given by the combination formula `C(n, 2)`. ## Algorithm 1. Read the input value `n`. 2. Calculate the number of handshakes using the formula: \[ \text{handshakes} = \frac{n \times (n - 1)}{2} \] 3. Output the result. ## Code Implementation

#include <iostream>
using namespace std;

// Function to calculate the number of handshakes
int calculateHandshakes(int n) {
    // Using the combination formula C(n, 2)
    return (n * (n - 1)) / 2;
}

int main() {
    int n;
    cout << "Enter the number of friends: ";
    cin >> n;
    
    // Calculate and output the number of handshakes
    cout << "Total handshakes: " << calculateHandshakes(n) << endl;
    
    return 0;
}

### Explanation of the Code - **Function `calculateHandshakes`**: This function takes an integer `n` and returns the number of handshakes using the combination formula. - **Main Function**: Reads the input value `n`, calls the `calculateHandshakes` function, and prints the result. ## Complexity Analysis - **Time Complexity**: O(1) - The calculation involves a constant number of operations. - **Space Complexity**: O(1) - No additional space is required beyond the input and a few variables. ## Edge Cases - **Minimum Input**: When `n = 1`, the output should be `0` as there are no other friends to shake hands with. - **Large Input**: The solution should handle large values of `n` efficiently due to its O(1) complexity. ### Example Edge Cases 1. **Input**: `n = 1` **Output**: `0` 2. **Input**: `n = 1000000000` **Output**: `499999999500000000` ## Testing To test the solution comprehensively, consider the following test cases: 1. Simple cases with small `n` values. 2. Edge cases with `n = 1`. 3. Large values of `n` to ensure the solution handles them efficiently. ## Conclusion Understanding and solving combinatorial problems like this one is crucial for developing strong problem-solving skills. The optimized solution using the combination formula is efficient and elegant, making it suitable for large inputs. ## Additional Resources - [Combinatorics and Permutations](https://en.wikipedia.org/wiki/Combinatorics) - [C++ Documentation](https://en.cppreference.com/w/) - [LeetCode](https://leetcode.com/) for more practice problems. By practicing similar problems and understanding the underlying principles, you can improve your problem-solving skills and tackle more complex challenges with confidence.