Count Even Numbers
Given 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
- numsinteger-array
- the list of integers to check
- Returnsinteger
- the number of even values in nums
Constraints
1 ≤ nums.length ≤ 5000-109 ≤ nums[i] ≤ 109
Examples
- Input
- nums = [3, 8, 12, 5, 6]
- Output
- 3
- Explanation
8,12and6divide by2with nothing left over;3and5do not. The answer is3.
- Input
- nums = [-4, -3, 0, 7]
- Output
- 2
- Explanation
-4 = 2 × (-2)and0 = 2 × 0, so both are even.-3and7are odd, and the count is2.
- Input
- nums = [1, 9, 15]
- Output
- 0
- Explanation
1,9and15are all odd, so the answer is0.
Follow-up
You get many questions: how many even values lie between index l and index r? After one pass over nums, can you answer each in O(1) time?
Hints
Open them one at a time. Each one gives away a little more.
What is left over when you divide an even number by
2?A value
xis even exactly whenx % 2is0. Watch out: for a negative odd number, some languages give-1as the remainder, not1.Start a counter at
0, read every value once, and add1whenever the remainder by2is0.
Solution
Check each value once and count those that leave remainder 0 when divided by 2. Comparing the remainder with 0, rather than testing for odd with 1, keeps negative numbers right.
Collect the even values, then count them
Intuition
Pick out the even values with a filter, then return the length of the result. For [3, 8, 12, 5, 6] the filtered list is [8, 12, 6], so the answer is 3.
The time is O(n), but the new list costs O(n) memory, up to 5000 values, only to read its length once.
Algorithm
- Build a new list holding every
xinnumswithx % 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, and add 1 for each value with x % 2 == 0. An even number leaves remainder 0 whatever its sign, so the test holds for -4 and 0 in every language. A test for odd written x % 2 == 1 does not: in C, Java, JavaScript and most C-like languages the remainder takes the sign of the number, so -3 % 2 is -1.
One pass and one integer: O(n) time, O(1) space.
Algorithm
- Set
countto0. - Loop over every value
xinnums. - If
x % 2 == 0, add1tocount. - 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
- Counting the odd values with
x % 2 == 1and subtracting from the length. In C-like languages-3 % 2is-1, so[-3]returns 1 instead of 0. - Treating
0as neither even nor odd.0 = 2 × 0, so[0]returns1. - Writing the bit test as
x & 1 == 0. In C, C++ and JavaScript,==binds tighter than&, so it meansx & (1 == 0), which is always0and counts nothing. Write(x & 1) == 0.
Frequently asked questions3
How do you check if a number is even in code?
Test whether the remainder after dividing by 2 is zero: x % 2 == 0. It works for positive numbers, negative numbers and zero, even in languages where -3 % 2 is -1. You can also check the lowest bit with (x & 1) == 0.
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, where an even number belongs.
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).
Similar problems
Problems that use the same ideas. Solving two or three of them is what makes a pattern stick.
def countEvens(nums):
# Write code hereTest #1
Test #2
Test #3
Argument
nums = [3, 8, 12, 5, 6]
Expected Output
3