Count Even Numbers

Q: How do you check if a number is even in code?

Test whether the remainder after dividing by 2 is zero: x % 2 == 0 . This works for positive numbers, negative numbers and zero in every mainstream language. Another way is to check the lowest bit with (x & 1) == 0 , since even numbers end in a 0 bit.

Q: Is zero an even number?

Yes. Zero divided by 2 is 0 with no remainder, so it fits the definition of even. It also sits between the odd numbers -1 and 1 , exactly where an even number belongs.

Q: What is the time complexity of counting even numbers in an array?

One pass with a counter takes O(n) time and O(1) extra space. Every value has to be checked, so no method is faster than O(n) . Building a filtered list first gives the same count but uses O(n) extra memory.

BeginnerArrays and strings Math and simulation

+10

You get a non-empty list of integers nums. Return how many of its values are even. A number is even when dividing it by 2 leaves no remainder, which includes 0 and negative numbers such as -4.

Function

countEvens(nums: integer-array) → integer

numsinteger-array: the list of integers to check
Returnsinteger: the number of even values in nums

Constraints

1 ≤ nums.length ≤ 5000
-10⁹ ≤ nums[i] ≤ 10⁹

Examples

Input: nums = [3, 8, 12, 5, 6]
Output: 3
Explanation: 8, 12 and 6 divide by 2 with nothing left over, while 3 and 5 leave a remainder. That makes 3 even values.

Input: nums = [-4, -3, 0, 7]
Output: 2
Explanation: -4 = 2 × (-2) and 0 = 2 × 0, so both are even. -3 and 7 are odd, and the count is 2.

Input: nums = [1, 9, 15]
Output: 0
Explanation: 1, 9 and 15 are all odd, so no value counts and the answer is 0.

+12 hidden tests on Submit

Follow-up

You get many questions of the form: how many even values lie between index l and index r? After one pass over nums, can you answer each question in O(1) time?

Hints

Open them one at a time. Each one gives away a little more.

0 of 3 opened

Solution

The loop is one line; the evenness test is where solutions break. In many languages the remainder of a negative number is negative, so -3 % 2 is -1. Testing x % 2 == 0 is right for every sign in every language, and a running counter needs no extra memory.

Collect the even values, then count them

Intuition

Split the task into two steps: pick out the even values, then count what you picked. A value x is even when x % 2 == 0. Most languages have a filter function that builds the new list in one line, and its length is the answer. For [3, 8, 12, 5, 6] the filtered list is [8, 12, 6], so the answer is 3.

This is correct and reads well, but the new list costs O(n) memory, up to 5000 values here, only to read its length once. The values themselves are never used again.

Algorithm

Build a new list holding every x in nums with x % 2 == 0.
Return the length of that list.

def countEvens(nums):
    evens = [x for x in nums if x % 2 == 0]
    return len(evens)

Count with a running counter

Intuition

Keep a counter instead of a list. Start it at 0, look at each value once, and add 1 when the value is even. Every value is checked exactly once, so the count is exact, and the only memory is one integer.

The test deserves care. In C, C++, Java, C#, JavaScript, Go, Rust, Swift and PHP the remainder takes the sign of the number, so -3 % 2 is -1, not 1. An even number leaves remainder 0 whatever its sign, so x % 2 == 0 is always right, while an odd test written as x % 2 == 1 misses every negative odd number. For [-4, -3, 0, 7] the remainders are 0, -1, 0 and 1, so the counter ends at 2.

Zero counts as well: 0 % 2 is 0, so 0 is even.

Algorithm

Set count to 0.
Loop over every value x in nums.
If x % 2 == 0, add 1 to count.
After the loop, return count.

def countEvens(nums):
    count = 0
    for x in nums:
        if x % 2 == 0:  # 0 also works for negatives, where the remainder can be -1
            count += 1
    return count

Pitfalls and edge cases

The bugs here come from negative numbers and from zero.

Counting the odd values with x % 2 == 1 and subtracting from the length. In C-like languages -3 % 2 is -1, so -3 is never counted as odd and ends up counted as even.
Treating 0 as neither even nor odd. 0 = 2 × 0, so it is even, and [0] returns 1.
Writing the bit test as x & 1 == 0. In C, C++ and JavaScript, == binds tighter than &, so it means x & (1 == 0), which is always 0 and counts nothing. Write (x & 1) == 0.
Starting the loop at index 1 in a 0-based language, which skips the first value, or at 0 in Lua and R, where the first value is at index 1.

Frequently asked questions4

How do you check if a number is even in code?

Test whether the remainder after dividing by 2 is zero: x % 2 == 0. This works for positive numbers, negative numbers and zero in every mainstream language. Another way is to check the lowest bit with (x & 1) == 0, since even numbers end in a 0 bit.

Is zero an even number?

Yes. Zero divided by 2 is 0 with no remainder, so it fits the definition of even. It also sits between the odd numbers -1 and 1, exactly where an even number belongs.

Why does x % 2 == 1 fail for negative numbers?

In C, C++, Java, C#, JavaScript, Go, Rust, Swift and PHP, the remainder takes the sign of the number being divided, so -3 % 2 is -1. Python, Ruby, Dart, Lua and R return 1 instead. Testing x % 2 != 0 for odd and x % 2 == 0 for even gives the same answer in all of them.

What is the time complexity of counting even numbers in an array?

One pass with a counter takes O(n) time and O(1) extra space. Every value has to be checked, so no method is faster than O(n). Building a filtered list first gives the same count but uses O(n) extra memory.

Python

def countEvens(nums):
    # Write code here

Test cases

Case 1

Case 2

Case 3

Input

nums = [3, 8, 12, 5, 6]

Expected