odd elements in an array

Problem Statement

Given an integer array nums, return the number of odd elements present in the array.

Approach 1

Traverse the array and check whether each element leaves a non-zero remainder when divided by 2.

Maintain oddCount to record how many elements satisfy this condition. Using a non-zero remainder check also handles negative odd numbers correctly.

Algorithm

• Initialize oddCount with 0, where it keeps track of how many odd elements have been found so far.

• Traverse the array once so that every element can be checked for oddness.

• For each element, check nums[i] % 2 != 0. A non-zero remainder means the current value is odd, and this condition also works correctly for negative odd numbers.

• Whenever the condition is satisfied, increment oddCount to include the current element in the count.

• Return oddCount after all elements have been checked.

Dry Run

Solution

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 oddCount requires auxiliary storage.

Approach 2

The least significant bit of an odd integer is always 1.

Performing a bitwise AND operation with 1 checks this final bit. When (num & 1) is non-zero, the number is odd.

Algorithm

• Initialize oddCount with 0, where it stores the number of odd elements found during traversal.

• Traverse every element of nums so that its least significant bit can be checked.

• For each element, evaluate (nums[i] & 1). An odd number always has its least significant bit set to 1.

• When (nums[i] & 1) != 0, increment oddCount because the current element is odd.

• Return oddCount once the complete array has been processed.

Dry Run

Solution

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 oddCount requires auxiliary storage.

FAQs

Q1. Why should num % 2 != 0 be used instead of num % 2 == 1?

For negative odd numbers, some languages produce -1 as the remainder after division by 2. Checking for a non-zero remainder correctly handles both positive and negative odd values.

Q2. Is zero considered an odd number?

No. Zero is perfectly divisible by 2, so it is even and must not be included in the odd count.

Q3. Which approach should be preferred in an interview?

The modulo approach is generally preferred because it clearly expresses the mathematical definition of an odd number. The bitwise approach may be discussed as an alternative.

Q4. Can the even count be calculated without another traversal?

Yes. After finding oddCount, the number of even elements can be calculated as nums.length - oddCount.

Q5. Can this problem be solved faster than O(N)?

No. Every element must be examined because any unchecked element could be odd. Therefore, O(N) time is optimal.

Q6. What should be returned when the array is empty?

The answer should be 0 because an empty array contains no odd elements.