Start learning free

LESSON 193 OF 338 · NESTED LOOPS & BRUTE FORCE

Pair Count in Go: O(n^2) Nested Loops

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:
			result += 1
return result


STEP 1 OF 5
    Ctrl + Enter to check

    GO · NESTED LOOPS & BRUTE FORCE

    Pair Count in Go, explained

    Problem overview

    The function countPairs(n, sum int) int receives two positive integers. It must return how many different pairs (x, y) satisfy 1 <= x, y <= n and x + y == sum. The order inside a pair does not matter: (1, 5) and (5, 1) are the same pair.

    For n = 7 and sum = 6 the pairs are (1, 5), (2, 4) and (3, 3), so the answer is 3. A pair may use the same number twice, as (3, 3) does.

    The target complexity is O(n^2) time and O(1) space, which is what a brute force over all pairs costs.

    Approach: try every candidate pair

    Brute force means checking every candidate and counting those that work. Because order does not matter, the candidates are the pairs with x <= y. Each such pair appears exactly once, so the count needs no correction afterwards.

    That gives two nested loops: the outer loop picks x from 1 to n, and the inner loop picks y from x to n. Starting y at x rather than at 1 does two things. It skips the mirrored pairs such as (5, 1), and it still includes (x, x). A counter records each pair whose two numbers add up to sum.

    There are about n^2 / 2 candidates, so the time is O(n^2). Only a counter and two loop variables are stored, so the space is O(1).

    Why brute force is acceptable here

    The lesson asks for the quadratic version on purpose. It is the simplest correct answer: every candidate is examined, so nothing can be missed, and the condition i+j == sum is written exactly as the problem states it. For small n the cost is negligible. It also trains a pattern that returns in many later problems: two nested loops where the inner one starts at the outer index (or just after it), so that each unordered pair is visited once.

    Once x is fixed, the only y that can work is sum - x, so the inner loop could be replaced by a direct check. That idea leads to a faster solution, but it needs care with the bounds and with the case x == y. The nested loops avoid those details.

    Step by step

    1. Declare result with := and the value 0. It counts the pairs found so far.
    2. Loop over the first number with i from 1 while i <= n. The bounds start at 1 and include n because the problem says 1 <= x <= n.
    3. Loop over the second number with j starting at i and running while j <= n. Starting at i counts each unordered pair once.
    4. Check the sum. If i+j == sum, this pair is a solution, so increment result. In Go, result++ is a statement on its own, not an expression you can use inside another one.
    5. Return result after both loops finish.

    The solution in Go

    func countPairs(n, sum int) int {
    result := 0
    for i := 1; i <= n; i++ {
        for j := i; j <= n; j++ {
            if i+j == sum {
                result++
            }
        }
    }
    return result
}

    Go details:

    • n, sum int declares two parameters of the same type; the type is written once after the last name.
    • := declares and initializes in one step, and the type of result is inferred as int. An unused variable would be a compile error, but here result is returned.
    • The loop variables i and j exist only inside their loops. The inner j is created anew on every pass of the outer loop.
    • The function must end with return because it has a result type.

    Complexity

    Time: O(n^2). The outer loop runs n times and the inner loop runs n - i + 1 times, so the body runs n + (n-1) + ... + 1 = n(n+1)/2 times, which is O(n^2).

    Space: O(1). The function keeps only result, i and j.

    Edge cases and common mistakes

    • Starting j at 1. This counts (1, 5) and (5, 1) separately, so countPairs(7, 6) would give 5 instead of 3.
    • Starting j at i + 1. This drops pairs like (3, 3), giving 2 for the example.
    • A sum that is too large. countPairs(3, 10) returns 0, because the largest possible sum is 6.
    • A sum that is too small. The smallest possible sum is 2, so a sum of 1 gives 0.
    • Using < instead of <=. The bound n is allowed, so j < n misses pairs such as (4, 4) when n = 4.

    Testing

    • n = 7, sum = 6 gives 3.
    • n = 1, sum = 2 gives 1, the pair (1, 1).
    • n = 3, sum = 10 gives 0.
    • n = 5, sum = 2 gives 1.
    • n = 10, sum = 11 gives 5.
    • n = 4, sum = 8 gives 1.
    Keep going with GoAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free