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.
Your algorithm should run in O(n^2) time and use O(1) space.
The problem requires counting the number of unique pairs (x, y) such that their sum equals a given value, and both x and y lie within the range [1, n].
Input: Two integers, n and sum.
Output: An integer representing the number of valid pairs.
Constraints:
Example:
Input: n = 7, sum = 6 Output: 3 Explanation: Valid pairs are (1, 5), (2, 4), and (3, 3).
The core challenge is to find pairs of integers within a specified range that add up to a given sum. This problem is significant in various applications such as finding pairs in arrays, solving two-sum problems, and more.
Potential pitfalls include counting duplicate pairs (e.g., (1, 5) and (5, 1)) and ensuring that pairs are within the specified range.
To solve this problem, we can use a brute force approach with nested loops to check all possible pairs. Although this approach is not optimal, it is straightforward and easy to understand.
We can then optimize the solution by reducing unnecessary checks and leveraging mathematical properties.
The naive solution involves using two nested loops to iterate through all possible pairs (x, y) and checking if their sum equals the given value.
int countPairs(int n, int sum) {
int result = 0;
for (int x = 1; x <= n; ++x) {
for (int y = x; y <= n; ++y) {
if (x + y == sum) {
result++;
}
}
}
return result;
}
This approach has a time complexity of O(n^2) and space complexity of O(1).
We can optimize the solution by reducing the range of the inner loop. Instead of iterating from x to n, we can iterate from max(1, sum - n) to min(n, sum - 1).
int countPairs(int n, int sum) {
int result = 0;
for (int x = 1; x <= n; ++x) {
int y = sum - x;
if (y >= x && y <= n) {
result++;
}
}
return result;
}
This approach still has a time complexity of O(n) but reduces unnecessary checks, making it more efficient.
1. Initialize a counter variable to store the number of valid pairs.
2. Iterate through all possible values of x from 1 to n.
3. For each x, calculate the corresponding y as sum - x.
4. Check if y is within the valid range and if y >= x to avoid counting duplicate pairs.
5. Increment the counter if the pair (x, y) is valid.
6. Return the counter value.
#include <iostream>
using namespace std;
// Function to count the number of valid pairs
int countPairs(int n, int sum) {
int result = 0;
for (int x = 1; x <= n; ++x) {
int y = sum - x;
// Check if y is within the valid range and y >= x
if (y >= x && y <= n) {
result++;
}
}
return result;
}
int main() {
int n = 7;
int sum = 6;
cout << "Number of valid pairs: " << countPairs(n, sum) << endl;
return 0;
}
The time complexity of the optimized solution is O(n) because we iterate through all possible values of x once. The space complexity is O(1) as we only use a few variables for counting and calculations.
Consider edge cases such as:
To test the solution comprehensively, consider a variety of test cases:
When approaching such problems, consider the following tips:
In this blog post, we discussed how to solve the problem of counting valid pairs with a given sum using a brute force approach and an optimized solution. We analyzed the complexity, considered edge cases, and provided a comprehensive code implementation in C++.
Understanding and solving such problems is crucial for developing problem-solving skills and improving algorithmic thinking.
For further reading and practice, consider the following resources: