Hand Shakes in Java - Time Complexity: O(1)

## 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 pair of friends shakes hands 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. ## Approach ### Naive Solution A naive solution would involve iterating through each pair of friends and counting the handshakes. However, this approach is not optimal and has a time complexity of O(n^2), which is infeasible for large values of `n`. ### Optimized Solution The problem can be solved using combinatorial mathematics. The number of ways to choose 2 items from `n` items is given by the combination formula: \[ C(n, 2) = \frac{n \times (n - 1)}{2} \] This formula directly gives us the number of unique pairs (handshakes) without the need for iteration, making the solution very efficient with a time complexity of O(1). ### Algorithm 1. **Input**: Read the integer `n`. 2. **Formula**: Use the combination formula to calculate the number of handshakes. 3. **Output**: Print the result. ## Code Implementation Here is the Java code to solve the problem:

public class HandShakes {
    public static int countHandShakes(int n) {
        // Using the combination formula C(n, 2) = n * (n - 1) / 2
        return (n * (n - 1)) / 2;
    }

    public static void main(String[] args) {
        int n = 3; // Example input
        System.out.println("Total handshakes: " + countHandShakes(n));
    }
}

### Explanation of the Code - **countHandShakes**: This method takes an integer `n` and returns the number of handshakes using the combination formula. - **main**: This method demonstrates the usage of `countHandShakes` with an example input. ## Complexity Analysis - **Time Complexity**: O(1) - The formula calculation is constant time. - **Space Complexity**: O(1) - No additional space is required. ## Edge Cases - **n = 1**: Only one person, so no handshakes. The output should be `0`. - **n = 2**: Two people, one handshake. The output should be `1`. - **Large n**: The formula handles large values efficiently due to its O(1) complexity. ## Testing To test the solution comprehensively, consider the following test cases: 1. **Simple Case**: `n = 3` (Expected output: `3`) 2. **Single Person**: `n = 1` (Expected output: `0`) 3. **Two People**: `n = 2` (Expected output: `1`) 4. **Large Number**: `n = 1000000` (Expected output: `499999500000`) ## Conclusion Understanding and solving combinatorial problems like this one is crucial for developing efficient algorithms. The key takeaway is to recognize the problem as a combination problem and apply the appropriate formula to achieve an optimal solution. ## Additional Resources - [Combinatorics and Permutations](https://en.wikipedia.org/wiki/Combinatorics) - [Java Math Library](https://docs.oracle.com/javase/8/docs/api/java/lang/Math.html) - [LeetCode](https://leetcode.com/) for more practice problems. By practicing such problems, you can enhance your problem-solving skills and prepare for coding interviews effectively.