Start learning free

LESSON 149 OF 414 · LOOPS & GLOBAL VARIABLES

Odd Numbers Versus Even Numbers in Scala

Practice Read the full explanation

Given an array, return true if there are more odd numbers than even numbers, otherwise return false.

Example:

Input: numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9]
Output: true

Explanation:
There are 5 odd numbers in the array: 1, 3, 5, 7, 9
There are 4 even numbers in the array: 2, 4, 6, 8
5 is greater than 4, so our function should return true
STEP 1 OF 5
    Ctrl + Enter to check

    SCALA · LOOPS & GLOBAL VARIABLES

    Odd Even in Scala, explained

    Problem overview

    The method oddEven receives an array of integers, numbers. It returns true if the array holds more odd numbers than even numbers, and false otherwise. A tie returns false, because "more" means strictly more.

    In the example Array(1, 2, 3, 4, 5, 6, 7, 8, 9) there are five odd numbers (1, 3, 5, 7, 9) and four even numbers (2, 4, 6, 8). Five is greater than four, so the result is true.

    Approach: two counters and one comparison

    The method needs two totals: how many odd numbers and how many even numbers it has seen. Walk through the array once. For each element, decide whether it is odd or even and increase the matching counter. When the walk is finished, compare the two counters and return whether the odd one is bigger.

    You don't need the numbers themselves afterwards, only the two counts. Because every integer is either odd or even, a single if with an else covers every element.

    For the example, the two counters change like this as the loop moves along:

    numberOdd?oddNumbersevenNumbers
    1yes10
    2no11
    3yes21
    4no22
    5 to 9odd, even, odd, even, odd54

    A first idea might be to copy the odd numbers into one array and the even numbers into another, and compare their lengths. That works but allocates memory that grows with the input, while counters need none. Since only the sizes matter, counting is enough.

    Step by step

    1. Declare oddNumbers and evenNumbers with var, both 0. Each goes on its own line. They change in the loop, so they can't be val. Scala infers Int from the literal.
    2. Loop with for (number <- numbers). The body runs once for each element, with number holding the current one.
    3. Test oddness with number % 2 != 0 and add 1 to oddNumbers when it holds. The next section explains why the test is "not 0" and not "equals 1". Scala has no ++, so the increment is += 1.
    4. Add an else branch that increments evenNumbers. It runs exactly when the condition is false, which means the remainder was 0.
    5. Return oddNumbers > evenNumbers. A comparison is already a Boolean, so it can be returned directly without an if.

    The solution in Scala

    class Solution {
    def oddEven(numbers: Array[Int]): Boolean = {
        var oddNumbers = 0
        var evenNumbers = 0
        for (number <- numbers) {
            if (number % 2 != 0) {
                oddNumbers += 1
            } else {
                evenNumbers += 1
            }
        }
        return oddNumbers > evenNumbers
    }
}

    Why != 0 and not == 1

    The remainder operator % in Scala takes the sign of the left operand. For positive numbers that gives the familiar results: 3 % 2 is 1 and 4 % 2 is 0. For negative numbers the remainder of an odd value is -1:

    3 % 2   // 1
-3 % 2  // -1
-4 % 2  // 0

    A test written as number % 2 == 1 would treat -3 as not odd, and count it as even. The test number % 2 != 0 works for both signs, because every odd number, positive or negative, has a nonzero remainder. For Array(-3, -5, 2) the correct method returns true, since two of the three numbers are odd.

    Other details

    • The loop variable number is read-only inside the body.
    • The parentheses around for (number <- numbers) hold a generator. The arrow reads "for each number in numbers".
    • Another way to ask whether an Int is odd is the bitwise test (number & 1) != 0, which also works for negative values. The remainder test is easier to read for most learners.
    • Returning a comparison directly is shorter than if (...) true else false and means the same.

    A single counter

    The question only asks which count is larger, so one variable can do the job of two. Add 1 for an odd number and subtract 1 for an even one, and return whether the balance ends above 0:

    var balance = 0
for (number <- numbers) {
    if (number % 2 != 0) balance += 1 else balance -= 1
}
balance > 0

    This gives the same results as the two-counter version on every input: true for the example and for Array(-3, -5, 2), false for a tie and for an empty array. The two-counter version is easier to read, and it is the one the lesson asks for.

    Complexity

    One pass over n numbers with constant work for each gives O(n) time. The method stores two counters and the loop variable, so the extra space is O(1).

    Edge cases and common mistakes

    • A tie. With the same number of odd and even values, such as Array(1, 2), the result is false. Writing >= would be a bug.
    • An empty array. Both counters stay 0, 0 is not greater than 0, and the result is false.
    • Negative numbers. Test with != 0, as above.
    • Zero. It is even, since 0 % 2 is 0, so it increments evenNumbers.
    • Extreme values. Int.MaxValue (2147483647) is odd and its remainder is 1. Int.MinValue (-2147483648) is even and its remainder is 0. The test needs no special care at either end of the range.
    • Swapped counters. If the odd branch increments evenNumbers by mistake, the method answers the opposite question for every input. Tracing the example by hand, as in the table above, catches this at once.
    • Returning the counts. The method returns a Boolean, not a number.

    Testing

    Try Array(1, 2, 3, 4, 5, 6, 7, 8, 9) (true), Array(-3, -5, 2) (true), Array(1, 2) (false) and an empty array (false).

    Keep going with ScalaAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free