Pair Count in O(n^2) Time Complexity using JavaScript

Given two positive integers n and sum, count the number of different pairs of integers (x, y) such that 1 <= x, y <= n and x + y equals sum

Example:

Input: n = 7, sum = 6
Output: 3
Explanation: There are 3 valid pairs: (1, 5), (2, 4), (3, 3).

Note that pairs such as (1, 5) and (5, 1) are not considered different.

Note:

Your algorithm should run in O(n^2) time and use O(1) space.

Problem Definition

Given two positive integers n and sum, count the number of different pairs of integers (x, y) such that 1 <= x, y <= n and x + y equals sum.

Input: Two integers, n and sum.

Output: An integer representing the number of valid pairs.

Constraints:

1 <= n <= 10^4
1 <= sum <= 2 * n

Example:

Input: n = 7, sum = 6
Output: 3
Explanation: There are 3 valid pairs: (1, 5), (2, 4), (3, 3).

Understanding the Problem

The core challenge is to find pairs of integers within a given range that sum up to a specific value. This problem is significant in various applications such as finding pairs in arrays, solving two-sum problems, and more.

Potential pitfalls include counting pairs like (1, 5) and (5, 1) as different, which is incorrect as per the problem statement.

Approach

To solve this problem, we can start with a brute force approach and then discuss optimized solutions.

Naive Solution

The naive solution involves using two nested loops to check all possible pairs (x, y) and count those that sum up to the given value.

This approach is straightforward but not optimal as it has a time complexity of O(n^2).

Optimized Solution

We can optimize the solution by reducing the number of pairs we check. Instead of checking all pairs, we can use a single loop and calculate the complement of each number to see if it forms a valid pair.

Algorithm

Let's break down the algorithm step-by-step:

Naive Approach

function countPairs(n, sum) {
  let result = 0;
  // Iterate through all possible values of x
  for (let x = 1; x <= n; x++) {
    // Iterate through all possible values of y starting from x to avoid duplicate pairs
    for (let y = x; y <= n; y++) {
      // Check if the pair (x, y) sums up to the given value
      if (x + y === sum) {
        result++;
      }
    }
  }
  return result;
}

Optimized Approach

function countPairs(n, sum) {
  let result = 0;
  // Iterate through all possible values of x
  for (let x = 1; x <= n; x++) {
    // Calculate the complement y
    let y = sum - x;
    // Check if y is within the valid range and x <= y to avoid duplicate pairs
    if (y >= x && y <= n) {
      result++;
    }
  }
  return result;
}

Complexity Analysis

Naive Approach:

Time Complexity: O(n^2) - Due to the nested loops.
Space Complexity: O(1) - Only a few variables are used.

Optimized Approach:

Time Complexity: O(n) - Single loop with constant time operations inside.
Space Complexity: O(1) - Only a few variables are used.

Edge Cases

Consider the following edge cases:

n = 1, sum = 2: Only one pair (1, 1).
n = 10, sum = 20: No valid pairs as the maximum sum is 19.
n = 5, sum = 3: Pairs (1, 2) and (2, 1) should be counted as one.

Testing

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

console.log(countPairs(7, 6)); // Output: 3
console.log(countPairs(1, 2)); // Output: 1
console.log(countPairs(10, 20)); // Output: 0
console.log(countPairs(5, 3)); // Output: 1

Thinking and Problem-Solving Tips

When approaching such problems, consider the following tips:

Understand the problem constraints and requirements thoroughly.
Start with a brute force approach to get a basic solution.
Look for patterns or mathematical properties to optimize the solution.
Test with edge cases to ensure the solution handles all scenarios.

Conclusion

In this blog post, we discussed how to solve the problem of counting pairs of integers that sum up to a given value. We explored both naive and optimized approaches, analyzed their complexities, and provided comprehensive testing strategies. Understanding and solving such problems is crucial for developing strong problem-solving skills in programming.

Additional Resources

For further reading and practice, consider the following resources: