Start learning free

LESSON 212 OF 410 · BRUTE FORCE

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

Practice O(n2) Read the full explanation

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.


Hints:

Let's come up with a brute force approach. Brute force tries each and every candidate to our solution. For this problem, the candidates are all the pairs of numbers (x, y) such that 1 <= x <= y <= n. How can we try out all these pairs?

Using two nested for loops! The first loop will try out each possible x between 1 and n. The second loop will be written inside the first one and will try out each possible y between x and n. 
for each x : 1 -> n:
	for each y : x -> n:
What should be written inside these loops?

Inside the loops we should check if the pair (x, y) is a solution, e.g. if x + y == sum. If so, we should add 1 to the answer. But where do we store the answer? We'll need a variable for that. Let's name it result. 
result = 0
for each x : 1 -> n:
	for each y : x -> n:
		if x + y == sum:
			add 1 to result
return result


STEP 1 OF 5
    Ctrl + Enter to check

    PYTHON · BRUTE FORCE

    Pair Count in Python, explained

    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 considering pairs like (1, 5) and (5, 1) as different, which they are not in this context.

    Approach

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

    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

    Given the constraints, the naive solution is acceptable. However, we can still discuss the thought process:

    • Use two nested loops to iterate through all possible pairs (x, y).
    • Check if the sum of the pair equals the given sum.
    • Count the valid pairs.

    Algorithm

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

    1. Initialize a counter variable to store the number of valid pairs.
    2. Use a nested loop to iterate through all possible pairs (x, y).
    3. For each pair, check if their sum equals the given sum.
    4. If the condition is met, increment the counter.
    5. Return the counter value as the result.

    Code Implementation

    def count_pairs(n, sum):
    # Initialize the result counter
    result = 0
    
    # Iterate through all possible pairs (x, y)
    for x in range(1, n + 1):
        for y in range(x, n + 1):
            # Check if the pair (x, y) sums up to the given value
            if x + y == sum:
                result += 1
    
    # Return the total count of valid pairs
    return result

# Example usage
n = 7
sum_value = 6
print(count_pairs(n, sum_value))  # Output: 3

    Complexity Analysis

    The time complexity of the above solution is O(n^2) due to the nested loops. The space complexity is O(1) as we are using a constant amount of extra space.

    Edge Cases

    Consider the following edge cases:

    • When n is 1 and sum is 2, the output should be 1.
    • When n is large and sum is small, ensure the algorithm handles it efficiently.

    Examples:

    Input: n = 1, sum = 2
Output: 1

Input: n = 10, sum = 3
Output: 1

    Testing

    To test the solution comprehensively, consider a variety of test cases:

    • Simple cases with small n and sum values.
    • Edge cases with minimum and maximum values of n and sum.
    • Random cases to ensure the algorithm handles all scenarios.

    Thinking and Problem-Solving Tips

    When approaching such problems:

    • Break down the problem into smaller parts.
    • Start with a brute force solution and then optimize.
    • Consider edge cases and test thoroughly.

    Conclusion

    Understanding and solving such problems is crucial for developing problem-solving skills. Practice regularly and explore different approaches to improve.

    Additional Resources

    For further reading and practice:

    Keep going with PythonAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free