Hand Shakes - Time Complexity: O(1) - JavaScript

There are n friends in a group. When they meet, everybody shakes hands with everybody. How many hand shakes happen?

Example:

Input: n = 3

Output: 3

Explanation:
Considering A, B, and C are the 3 friends.
The hand shakes are: (A, B), (A, C) and (B, C)

Understanding the Problem

The core challenge of this problem is to determine the number of unique handshakes that occur when each person in a group of n friends shakes hands with every other person exactly once. This problem is significant in combinatorics and has applications in network theory, social networking, and more.

Potential pitfalls include misunderstanding that each handshake is unique and not double-counting handshakes.

Approach

To solve this problem, we need to think about the nature of handshakes. Each person shakes hands with every other person exactly once. This can be visualized as a complete graph where each node represents a person and each edge represents a handshake.

Naive Solution

A naive solution would involve iterating through each pair of friends and counting the handshakes. However, this approach is not optimal as it involves nested loops, leading to a time complexity of O(n^2).

Optimized Solution

We can derive a formula to calculate the number of handshakes directly. For n friends, each person shakes hands with n-1 others. However, this counts each handshake twice (once for each participant), so we divide by 2. The formula is:

Number of handshakes = (n * (n - 1)) / 2

This formula is derived from the combination formula C(n, 2), which counts the number of ways to choose 2 items from n items without regard to order.

Algorithm

Here is a step-by-step breakdown of the algorithm:

Calculate the product of n and n-1.
Divide the result by 2 to account for double-counting.
Return the result.

Code Implementation

/**
 * Function to calculate the number of handshakes
 * @param {number} n - Number of friends
 * @return {number} - Number of handshakes
 */
function countHandshakes(n) {
  // Calculate the number of handshakes using the formula
  return (n * (n - 1)) / 2;
}

// Example usage:
const n = 3;
console.log(countHandshakes(n)); // Output: 3

Complexity Analysis

The time complexity of this solution is O(1) because it involves a constant number of arithmetic operations regardless of the input size. The space complexity is also O(1) as it uses a fixed amount of space.

Edge Cases

Potential edge cases include:

n = 0: No friends, so no handshakes. The output should be 0.
n = 1: One friend, so no handshakes. The output should be 0.

These cases are handled correctly by the formula as (0 * -1) / 2 and (1 * 0) / 2 both yield 0.

Testing

To test the solution comprehensively, consider the following test cases:

console.log(countHandshakes(0)); // Output: 0
console.log(countHandshakes(1)); // Output: 0
console.log(countHandshakes(2)); // Output: 1
console.log(countHandshakes(3)); // Output: 3
console.log(countHandshakes(4)); // Output: 6
console.log(countHandshakes(10)); // Output: 45

These test cases cover simple, edge, and larger cases to ensure the function works correctly.

Thinking and Problem-Solving Tips

When approaching such problems, consider the following tips:

Visualize the problem with small examples to understand the pattern.
Look for mathematical formulas or combinatorial principles that can simplify the problem.
Break down the problem into smaller, manageable parts.
Practice similar problems to improve problem-solving skills.

Conclusion

In this blog post, we discussed how to solve the problem of counting handshakes among n friends using a combinatorial approach. We derived an optimized formula, implemented it in JavaScript, and analyzed its complexity. Understanding such problems enhances your problem-solving skills and prepares you for more complex challenges.

Additional Resources

For further reading and practice, consider the following resources: