Start learning free

LESSON 216 OF 414 · BRUTE FORCE

Pair Count in Scala: O(n^2) 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

    SCALA · BRUTE FORCE

    Pair Count in Scala, explained

    Problem overview

    The method countPairs receives two positive integers, n and sum. It returns how many different pairs (x, y) satisfy 1 <= x, y <= n and x + y == sum. Two pairs that contain the same numbers in a different order count as one, so (1, 5) and (5, 1) are the same pair.

    With n = 7 and sum = 6 the valid pairs are (1, 5), (2, 4) and (3, 3), so the answer is 3. The pair (3, 3) counts once: x and y may be equal. The statement asks for O(n^2) time and O(1) space.

    Approach: try every candidate

    This is a brute-force problem: the number of candidate pairs is small enough to test them all. The only decision is how to list the candidates without counting any pair twice.

    If x and y were both allowed to range over 1 to n, every pair with different numbers would show up in both orders. Requiring x <= y fixes that: each unordered pair then has exactly one representation, with the smaller number first. The outer loop picks x from 1 to n, and the inner loop picks y from x to n. Starting the inner loop at x and not at 1 does the de-duplication, and it still allows x == y.

    The number of tested pairs is about n * (n + 1) / 2, which is O(n^2). Only a handful of variables are needed, so the space is O(1).

    The nested loops are not the only way. Once x is fixed, y must be exactly sum - x, so a single loop that checks whether sum - x lies between x and n would count the same pairs in O(n) time. This lesson sticks to the brute-force loops, which test every candidate and show the pattern you will reuse on harder problems.

    The example, traced

    For n = 7 and sum = 6, the outer loop visits i = 1 to 7, and the inner loop covers j from i up to 7:

    • For i = 1, the only j with 1 + j == 6 is 5. Count so far: 1.
    • For i = 2, the match is j = 4. Count: 2.
    • For i = 3, the match is j = 3, and the inner loop starts exactly at 3, so it is found. Count: 3.
    • For i = 4, the partner would be 2, but the inner loop starts at 4 and never goes back. No match.
    • For i = 5, 6 and 7, the partner would be 1, 0 and -1, all below i, so nothing is counted.

    The final value of result is 3. Every pair is found once, from its smaller member.

    Step by step

    1. Create the counter. Declare result with var and start it at 0. It has to be a var because it changes; a val couldn't be updated.
    2. Loop over the first number. Use i <- 1 to n. The word to makes a range that includes n, which is right because x can equal n.
    3. Loop over the second number. Inside it, use j <- i to n. Starting at i counts each pair once and keeps the pairs where both numbers are equal.
    4. Test and count. When i + j == sum, add one to result with += 1. Every match is a distinct pair, so each adds exactly 1. Scala has no ++ operator.
    5. Return. After the loops, write result as the last expression. In Scala the last expression of a method is its value, so no return is needed.

    The solution in Scala

    class Solution {
    def countPairs(n: Int, sum: Int): Int = {
        var result = 0
        for (i <- 1 to n) {
            for (j <- i to n) {
                if (i + j == sum) {
                    result += 1
                }
            }
        }
        result
    }
}

    Scala details:

    • to versus until. 1 to n includes n; 1 until n stops before it. Using until here would miss every pair that contains n.
    • The range can be empty. 1 to 0 is an empty range, so a loop over it runs zero times. No special case is needed for a small n.
    • var and the final line. result is read at the end like any value. The bare result on the last line is the method's return value, and it has to be the last expression of the method.
    • Int arithmetic. Int is 32 bits and wraps around silently. i + j can't overflow here unless n is close to the largest Int, and a loop of that size would be far too slow anyway.

    Complexity

    Time: O(n^2). For i = 1 the inner loop makes n passes, for i = 2 it makes n - 1, and so on down to 1. The total is n + (n - 1) + ... + 1, which is n * (n + 1) / 2. Each pass does constant work.

    Space: O(1). The method holds result and two loop variables, whatever n is.

    Edge cases and common mistakes

    • Sum too small. The smallest possible sum is 1 + 1 = 2. With sum = 1 no pair works, and the method returns 0.
    • Sum too large. The largest sum is n + n. countPairs(3, 100) returns 0.
    • Equal numbers. countPairs(4, 8) returns 1, for (4, 4), and countPairs(5, 2) returns 1, for (1, 1).
    • Starting the inner loop at 1. That counts (1, 5) and (5, 1) separately. For n = 7 and sum = 6 it gives 5 and not 3.
    • Starting the inner loop at i + 1. That drops pairs with equal numbers, such as (3, 3).
    • Using until n. It leaves out n itself.

    Testing

    • countPairs(7, 6) gives 3.
    • countPairs(1, 2) gives 1.
    • countPairs(4, 8) gives 1.
    • countPairs(3, 100) gives 0.
    Keep going with ScalaAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free