Start learning free

LESSON 217 OF 415 · BRUTE FORCE

Pair Count in Swift: 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

    SWIFT · BRUTE FORCE

    Pair Count in Swift, explained

    Problem overview

    The method countPairs(_ n: Int, _ sum: Int) receives two positive integers. It must count the pairs of integers (x, y) with 1 <= x, y <= n and x + y == sum. The pairs (1, 5) and (5, 1) count as the same pair, so each pair is counted once.

    For n = 7 and sum = 6, the valid pairs are (1, 5), (2, 4) and (3, 3), so the answer is 3. Note that (3, 3) counts: a number can pair with itself, because the problem only limits the values, not whether they differ.

    The statement asks for O(n^2) time and O(1) space, which is a hint to try every candidate pair.

    Approach: try every pair once

    Brute force means checking each candidate and keeping the ones that qualify. Here the candidates are the pairs of numbers from 1 to n. Two nested loops generate them: the outer loop picks x, the inner loop picks y, and an if tests the sum.

    The one design choice is the inner loop's start. If both loops ran from 1 to n, the code would count (1, 5) and (5, 1) separately and give 5 for the example. Starting the inner loop at the outer value, so that x <= y, visits each unordered pair exactly once. It also keeps (3, 3), since the inner loop's first value equals the outer one. Picture the pairs as a grid of x against y: the nested loops walk only the half on and above the diagonal, where y is at least x.

    A faster idea exists, since for a given x the partner is sum - x, but this lesson practises the nested-loop pattern, so it checks every pair.

    Step by step

    1. Create the counter. var result = 0. It is a var because it grows during the search.
    2. Loop over the first number. for i in 1...n uses a closed range, which includes n. The range 1..<n would leave n out.
    3. Loop over the second number. for j in i...n starts at i instead of 1. That avoids counting the same pair in two orders and keeps pairs of equal numbers.
    4. Test the pair. If i + j == sum, add 1 with result += 1. Swift has no ++ operator, so += 1 is the way to add one.
    5. Return the count after both loops finish.

    The solution in Swift

    class Solution {
    func countPairs(_ n: Int, _ sum: Int) -> Int {
        var result = 0
        for i in 1...n {
            for j in i...n {
                if i + j == sum {
                    result += 1
                }
            }
        }
        return result
    }
}

    The Swift details worth knowing:

    • Closed ranges. 1...n includes both ends, and i...n includes n. The loop variable is a constant inside the body, so you cannot change i or j.
    • A range cannot run backwards. 1...n is only valid when n is at least 1. With n = 0 the program crashes at run time, because a range whose end is below its start is an error. The lesson's inputs are positive, so this never arises there, but guard against it if n might be 0.
    • Underscore labels. The parameters are declared _ n and _ sum, so callers write countPairs(7, 6) with no labels.

    Tracing the example

    With n = 7 and sum = 6, the outer loop visits 1 through 7:

    • i = 1: j runs from 1 to 7. Only j = 5 gives a sum of 6, so result becomes 1.
    • i = 2: j runs from 2 to 7. Only j = 4 matches, so result becomes 2.
    • i = 3: j runs from 3 to 7. j = 3 matches, so result becomes 3.
    • i = 4 to 7: even the smallest sum, i + i, is at least 8, so nothing matches and the result stays 3.

    The loop-free shortcut

    For each x the only possible partner is sum - x. It forms a counted pair when it is at least x, which keeps each pair in one order, and at most n:

    func fast(_ n: Int, _ sum: Int) -> Int {
    var result = 0
    for x in 1...n {
        let y = sum - x
        if y >= x && y <= n { result += 1 }
    }
    return result
}

    It returns the same answers as the nested version, for example 3 for fast(7, 6) and 5 for fast(10, 11), but runs in O(n) time. The lesson asks for the nested version so that brute force over pairs becomes familiar.

    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)/2 checks, which grows as n^2. Starting the inner loop at i halves the work compared with two full loops, but the order of growth is the same.

    Space: O(1). The code keeps only the counter and the two loop variables, whatever the value of n.

    Edge cases and common mistakes

    • Counting both orders. With the inner loop starting at 1, countPairs(7, 6) returns 5 instead of 3.
    • Dropping pairs of equal numbers. Starting the inner loop at i + 1 skips (3, 3) and returns 2 for the example.
    • A sum that is too big. The largest possible sum is 2 * n. countPairs(5, 20) returns 0, and so does countPairs(5, 1), since the smallest sum is 2.
    • The extreme sums. countPairs(5, 2) returns 1, for (1, 1), and countPairs(4, 8) returns 1, for (4, 4).
    • Even and odd sums. countPairs(10, 10) returns 5: (1, 9), (2, 8), (3, 7), (4, 6) and (5, 5). countPairs(10, 11) also returns 5, with no pair of equal numbers.
    • Using 1..<n. It leaves out n, so pairs involving n are missed.

    Testing

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