Start learning free

LESSON 219 OF 414 · BRUTE FORCE

Pair Count in Rust: O(n^2) Brute Force with 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:
			add 1 to result
return result


STEP 1 OF 5
    Ctrl + Enter to check

    RUST · BRUTE FORCE

    Pair Count in Rust, explained

    Problem overview

    The function count_pairs(n: i32, sum: i32) -> i32 receives two positive integers. It must count the pairs (x, y) with 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, so it is counted once.

    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, which is why (3, 3) counts. The statement asks for O(n^2) time and O(1) extra space.

    Approach: try every candidate once

    Brute force means checking each candidate answer and keeping the ones that qualify. The candidates here are the pairs, so the question is how to list each of them exactly once.

    If both numbers ran over 1 to n independently, every unordered pair with different members would be visited twice, as (1, 5) and as (5, 1). The fix is to require x <= y. The outer loop picks x from 1 to n, and the inner loop picks y from x to n. Starting y at x instead of x + 1 keeps pairs like (3, 3), where both numbers are equal.

    Applied to the example, the pairs checked for x = 1 are (1, 1) to (1, 7), for x = 2 they are (2, 2) to (2, 7), and so on. Only three of them add up to 6.

    Step by step

    1. Declare the counter. let mut result: i32 = 0; starts at zero. It needs mut because it changes, and i32 because that is the function's return type.
    2. Loop over the first number with for i in 1..=n. The range 1..n would stop before n, but the problem includes n, so use the inclusive form 1..=n.
    3. Loop over the second number with for j in i..=n, inside the first loop. Starting at i is what counts each pair once.
    4. Test and count. If i + j == sum, add one with result += 1. Rust has no ++ operator. Every match is a different pair, so each one adds exactly one.
    5. Return result after both loops have finished.

    The solution in Rust

    impl Solution {
    fn count_pairs(n: i32, sum: i32) -> i32 {
        let mut result: i32 = 0;
        for i in 1..=n {
            for j in i..=n {
                if i + j == sum {
                    result += 1;
                }
            }
        }
        return result;
    }
}

    Some Rust details:

    • Ranges over i32. 1..=n iterates i32 values here, because n is an i32. No casts are needed, since nothing is used as an index.
    • Inclusive versus exclusive. a..b excludes b and a..=b includes it. If n is smaller than the start (for example j in i..=n with i > n), the range is simply empty and the loop does not run.
    • Explicit return. return result; works, and so would ending the function with result and no semicolon, which is the more common Rust style.
    • Immutable by default. Without mut, result += 1 is a compile error: you can't assign twice to an immutable variable.

    Tracing the example

    With n = 7 and sum = 6, result starts at 0 and the loops proceed like this:

    • For i = 1, j runs from 1 to 7. Only j = 5 gives 1 + 5 = 6, so result becomes 1.
    • For i = 2, j runs from 2 to 7. Only j = 4 matches, and result becomes 2.
    • For i = 3, j runs from 3 to 7. Only j = 3 matches, and result becomes 3.
    • For i = 4, every j is at least 4, so the sum is at least 8 and nothing matches. The same holds for i = 5, 6 and 7.

    The loops finish and the function returns 3. The trace also shows a possible shortcut: once i + j passes sum, larger values of j can't match, so the inner loop could stop early. The lesson does not need it, and the full loop stays within the required O(n^2).

    Complexity

    Time: O(n^2). The inner loop runs n times for i = 1, n - 1 times for i = 2, and so on down to once for i = n. That totals n * (n + 1) / 2 checks, which grows like n^2. Each check is a single addition and comparison.

    Space: O(1). The function keeps three integers, result, i and j, however large n is.

    Edge cases and common mistakes

    • The sum is too small. The smallest possible sum is 2, from (1, 1). With sum = 1 nothing matches and the result is 0.
    • The sum is too large. The largest sum is 2 * n. With n = 7, sum = 14 gives 1 (the pair (7, 7)) and sum = 15 gives 0.
    • A pair with equal members. For n = 1 and sum = 2 the answer is 1, from (1, 1). Starting the inner loop at i + 1 would miss it.
    • Counting both orders. Starting the inner loop at 1 gives 5 for n = 7 and sum = 6: the pairs (1, 5) and (5, 1), (2, 4) and (4, 2), and (3, 3). The answer should be 3.
    • Using 1..n. The exclusive range never tries n, so (7, 7) in the sum-14 case would be lost.
    • Integer size. The sum i + j is at most 2 * n, which fits in an i32 while n is below about 1.07 billion. Past that the addition would wrap silently in an optimized build, but a quadratic loop over that many values would never finish anyway. The counter itself can't overflow, because there are at most n matching pairs.
    • Large n. The loops do work proportional to n^2, so very large inputs take a long time. The lesson's sizes are meant for this brute force.

    Testing

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