Problem Statement
Given an integer array nums, return the number of even elements present in the array.
Example 1
Input: nums = [2, 5, 8, 11, 14]
Output: 3
Explanation: The even numbers are 2, 8, and 14. So, the count is 3.
Example 2
Input: nums = [1, 3, 5, 7]
Output: 0
Explanation: There are no even numbers in the array. So, the count is 0.
Approach 1
Traverse the array and check whether each element leaves a remainder of 0 when divided by 2.
Maintain evenCount to record how many elements satisfy this condition.
Algorithm
Initialize
evenCountwith0, where it keeps track of how many even elements have been found so far.Traverse every element of
numsso that each value can be checked for evenness.For the current element, check
nums[i] % 2 == 0. A remainder of0means the number is exactly divisible by2, so it is even.Whenever the condition is satisfied, increment
evenCountto include the current element in the count.Return
evenCountafter all elements have been processed.
Dry Run
Count Even Number in Array Appraoch 1 Dry Run.png
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: int countEvenNumbers(const vector<int>& nums) { // Stores how many even values have been found. int evenCount = 0; for (int value : nums) { // A zero remainder confirms that the current value is even. if (value % 2 == 0) { evenCount++; } } return evenCount; }};int main() { vector<int> nums = {3, 4, 0, -2}; Solution solution; cout << "Even count: " << solution.countEvenNumbers(nums) << endl; return 0;}Complexity Analysis
Time Complexity: O(N), where N represents the number of elements in the array. Every element is checked once.
Space Complexity: O(1), because only evenCount requires auxiliary storage.
Approach 2
The least significant bit of an even integer is always 0.
Performing a bitwise AND operation with 1 checks this final bit. When (num & 1) equals 0, the number is even.
Algorithm
Initialize
evenCountwith0, where it stores the number of even elements found during traversal.Traverse every element of
numsso that its least significant bit can be checked.For each element, evaluate
(nums[i] & 1). This isolates the last binary bit of the number.If
(nums[i] & 1) == 0, the last bit is0, which means the current number is even. IncrementevenCountin this case.Return
evenCountonce the complete array has been checked.
Dry Run
Count Even Number in Array Appraoch 2 Dry Run.png
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: int countEvenNumbers(const vector<int>& nums) { // Stores how many even values have been found. int evenCount = 0; for (int value : nums) { // AND with 1 checks whether the least significant bit is 0. if ((value & 1) == 0) { evenCount++; } } return evenCount; }};int main() { vector<int> nums = {3, 4, 0, -2}; Solution solution; cout << "Even count: " << solution.countEvenNumbers(nums) << endl; return 0;}Complexity Analysis
Time Complexity: O(N), where N represents the number of elements in the array. Every element is checked once.
Space Complexity: O(1), because only evenCount requires auxiliary storage.
Interview follow-up Questions
Yes. Zero is divisible by 2, and negative values such as -2 and -8 are also even because they leave no remainder when divided by 2.
Be the first to add a comment.