Start learning free

LESSON 193 OF 348 · NESTED LOOPS & BRUTE FORCE

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

    KOTLIN · NESTED LOOPS & BRUTE FORCE

    Pair Count in Kotlin, explained

    Problem overview

    The function countPairs(n: Int, sum: Int): Int receives two positive integers. It must count the pairs (x, y) with 1 <= x, y <= n whose sum is exactly sum. The order inside a pair doesn't matter: (1, 5) and (5, 1) are the same pair and count once.

    In the example, 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, as (3, 3) does.

    The statement asks for O(n^2) time and O(1) extra space, which is the cost of trying every pair while keeping only a few variables.

    Approach: try every candidate pair

    A brute-force solution generates every candidate and tests each one. Here a candidate is a pair of numbers from 1 to n, and the test is x + y == sum.

    Taking all ordered pairs would count (1, 5) and (5, 1) separately. To avoid that, the pairs are generated with x <= y. The first number runs from 1 to n, and the second runs from the first number up to n. Each unordered pair then appears exactly once, with its smaller number first. Starting the second number at the first number, not after it, keeps pairs such as (3, 3).

    Two nested loops do this. The outer loop picks the first number, the inner loop picks the second, and an if counts the matches.

    Step by step

    1. Create the counter. Declare result with var, because its value changes, and start it at 0. If no pair matches, 0 is the right answer.
    2. Loop over the first number. Use for (i in 1..n). The range 1..n includes n, which is what the statement needs because n is an allowed value.
    3. Loop over the second number. Inside it, use for (j in i..n). Starting at i is what makes each pair count once.
    4. Test and count. If i + j == sum, add 1 with result++. Every pair reaching this test is distinct, so each match adds exactly 1.
    5. Return the count after both loops have finished.

    For n = 7 and sum = 6, the pairs that match are (1, 5), (2, 4) and (3, 3). When i is 4 and j is 2, the combination isn't even generated, because j starts at 4.

    The solution in Kotlin

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

    The Kotlin details worth knowing:

    • var and val. A val can't be reassigned. Since result++ changes the variable, it must be a var.
    • Inclusive ranges. 1..n and i..n include both ends. 1 until n would stop at n - 1 and miss pairs that use n, such as (1, 7).
    • Empty ranges are safe. If the start is greater than the end, as with 1..0, the loop body never runs. For n = 0 the function returns 0.
    • The loop variables are fresh each pass. You can't assign to i or j, and you don't need to.
    • Int is 32 bits. The sum i + j wraps silently past 2147483647. The loops would take far too long before that matters, so it doesn't affect this lesson's sizes.
    • result++ as a statement. It adds 1 to result. Kotlin has no need for a separate statement terminator, so no semicolon follows.

    Complexity

    Time: O(n^2). For the first number i, the inner loop makes n - i + 1 passes. Adding these for i from 1 to n gives n + (n - 1) + ... + 1 = n(n + 1) / 2 passes, which is of the order of n^2. Each pass does a constant amount of work.

    Space: O(1). The function stores result and the two loop variables, no matter how large n is.

    The statement asks for exactly this brute force. The condition x + y == sum also means that for each x there is at most one possible y, namely sum - x. With that observation you could drop the inner loop and get O(n). The lesson practises nested loops, so it uses the plain version.

    Beyond the brute force

    Because y = sum - x is fixed once x is chosen, the answer is the number of values of x that satisfy two conditions. First, x >= 1 and y = sum - x <= n, which means x >= sum - n. Second, x <= y, which means x <= sum / 2 with integer division. So x runs from maxOf(1, sum - n) to sum / 2, and the count is the length of that range, or 0 when it is empty:

    fun countPairsFast(n: Int, sum: Int): Int {
    val lo = maxOf(1, sum - n)
    val hi = sum / 2
    return if (hi >= lo) hi - lo + 1 else 0
}

    For n = 7 and sum = 6, lo is 1 and hi is 3, which gives 3. For n = 7 and sum = 14, both are 7, which gives 1. For n = 7 and sum = 15, lo is 8 and hi is 7, so the result is 0. It agrees with the nested loops on all the examples below, and it runs in constant time. The lesson asks for the nested loops, though, because they are the pattern you will reuse when no formula exists.

    Edge cases and common mistakes

    • No pair exists. If sum is larger than 2 * n, as with n = 7 and sum = 15, the answer is 0. The same holds for sum = 1, since the smallest possible sum is 2.
    • Equal numbers. With n = 5 and sum = 2 the only pair is (1, 1), and the answer is 1. Starting the inner loop at i + 1 would miss it.
    • The largest sum. With n = 7 and sum = 14, the only pair is (7, 7), so the answer is 1. This one needs the inclusive end n in both loops.
    • Counting both orders. Starting the inner loop at 1 gives 5 for n = 7 and sum = 6, because it also counts (5, 1), (4, 2) and so on. The correct answer is 3.
    • Using until. Excluding n from either range loses pairs.
    • Declaring result with val. The compiler rejects result++ on a read-only variable.

    Testing

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