Start learning free

LESSON 192 OF 347 · NESTED LOOPS & BRUTE FORCE

Pair Count in C#: 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:
			result += 1
return result


STEP 1 OF 5
    Ctrl + Enter to check

    C# · NESTED LOOPS & BRUTE FORCE

    Pair Count in C#, explained

    Problem overview

    The method CountPairs(int n, int sum) counts the pairs of integers (x, y) with 1 <= x, y <= n and x + y == sum. Pairs that differ only in order count once, so (1, 5) and (5, 1) are the same pair.

    For n = 7 and sum = 6, the valid 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.

    Approach

    The lesson asks for O(n^2) time and O(1) extra space. That is a brute-force budget: try every candidate pair and test each one. No cleverness is needed, and the lesson's point is writing the two loops correctly.

    To count each unordered pair once, always put the smaller number first. Let i run from 1 to n, and let j run from i to n. Then every pair appears exactly once with i <= j, and (5, 1) is never visited because j would have to start below i.

    The loops try the pairs in this order for n = 7: (1, 1), (1, 2), ... (1, 7), then (2, 2) through (2, 7), and so on. The matches for sum = 6 are (1, 5), (2, 4) and (3, 3).

    Tracing the example

    With n = 7 and sum = 6, the check i + j == sum succeeds only when j equals 6 - i. Here is what each pass of the outer loop does:

    iValues of j triedMatching jresult afterwards
    11 to 751
    22 to 742
    33 to 733
    44 to 7none, because 2 is below 43
    55 to 7none3
    66 to 7none3
    77 to 7none3

    From i = 4 on, the partner 6 - i is smaller than i. That pair was already counted earlier, with the numbers the other way round, and the inner loop never goes back to look at it. This is exactly how starting j at i avoids double counting.

    Step by step

    1. Declare result. An int starting at 0 holds the count so far.
    2. Loop over the first number. i starts at 1 and runs while i <= n. The bound is inclusive because n itself is allowed.
    3. Loop over the second number. Inside it, j starts at i, not at 1, and runs while j <= n. Starting at i keeps every pair in order and allows i == j.
    4. Test and count. If i + j == sum, increment result. Each match is a different pair, so each adds exactly 1.
    5. Return result after both loops finish.

    The solution in C#

    class Solution {
    public int CountPairs(int n, int sum) {
        int result = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = i; j <= n; j++) {
                if (i + j == sum) {
                    result++;
                }
            }
        }
        return result;
    }
}

    Two details are worth a look. The loops use <= because the range 1 to n includes both ends, unlike the < array.Length bound you use for array indices. And result++ is shorthand for result = result + 1.

    C# details

    • Every variable is declared with its type. int result = 0; must be initialised before it is used. C# refuses to compile code that reads a local variable that may never have been assigned.
    • The loop variables are scoped to their loops. i exists only inside the outer loop and j only inside the inner one, and each new pass of the outer loop creates a fresh j that starts again at i.
    • Integer addition wraps silently. If i + j exceeded the int range, C# would not report an error by default; the result would wrap around to a negative number. It isn't a concern here, because a loop over n^2 pairs is only practical for modest n, where i + j is far from the limit.

    Another way to look at it

    You could count ordered pairs with two full loops from 1 to n, then fix the total: every pair with x != y was counted twice and every pair with x == y once. That needs extra bookkeeping. Starting the inner loop at i gives the right count directly.

    Complexity

    Time: O(n^2). For i = 1 the inner loop runs n times, for i = 2 it runs n - 1 times, and so on down to 1. The total is n + (n - 1) + ... + 1 = n(n + 1) / 2, which grows like n^2.

    Space: O(1). The method uses only result, i and j, whatever the size of n.

    The inner loop does a lot of pointless work: for each i, only one value of j can possibly match, namely sum - i. A faster version would check directly whether that value lies between i and n, which makes the whole method O(n). This lesson practises the nested-loop pattern, so it keeps the full search.

    Edge cases and common mistakes

    • Starting j at 1. This counts (1, 5) and (5, 1) separately, so the example would give 5 instead of 3.
    • Starting j at i + 1. This drops pairs with two equal numbers, such as (3, 3). The example would give 2.
    • Using < instead of <=. The loops would never try n itself. CountPairs(4, 8) must return 1, from (4, 4).
    • A sum that is too large or too small. If sum is bigger than 2 * n, no pair works and the answer is 0. CountPairs(3, 10) returns 0.
    • The smallest sum. CountPairs(5, 2) returns 1, from (1, 1).

    Testing

    • n = 7, sum = 6 gives 3.
    • n = 4, sum = 8 gives 1: only (4, 4) works, and it checks the inclusive bound and the equal-numbers case at once.
    • n = 3, sum = 10 gives 0, because the largest possible sum is 6.
    • n = 5, sum = 2 gives 1, from (1, 1), the smallest possible pair.
    • n = 1, sum = 2 gives 1: the loops run once, and (1, 1) matches.
    Keep going with C#About 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free