Bitwise OR of Even Numbers in an Array

Difficulty: Easy | Acceptance: 85.00% | Paid: No Topics: Array, Bit Manipulation, Simulation

You are given an integer array nums. Return the bitwise OR of all the even numbers in nums. If there are no even numbers, return 0.

The bitwise OR operation is a binary operation that compares the binary representation of two numbers bit by bit and returns a new number where each bit is set to 1 if at least one of the corresponding bits in the operands is 1, otherwise it is set to 0.

Table of Contents

• Examples
• Constraints
• Approach 1: Iterative Simulation
• Approach 2: Functional Programming (Filter & Reduce)
• Approach 3: Bitwise Check Optimization

Examples

Example 1

Input: nums = [1, 2, 3, 4]
Output: 6
Explanation: The even numbers in the array are 2 and 4.
2 in binary is 010.
4 in binary is 100.
2 | 4 = 110 (which is 6 in decimal).

Example 2

Input: nums = [1, 3, 5]
Output: 0
Explanation: There are no even numbers in the array. The bitwise OR of an empty set is 0.

Example 3

Input: nums = [2, 2, 2]
Output: 2
Explanation: The even numbers are 2, 2, and 2.
2 | 2 | 2 = 2.

Constraints

- 1 <= nums.length <= 100
- 1 <= nums[i] <= 100

Approach 1: Iterative Simulation

Intuition We iterate through the array once. For each number, we check if it is even using the modulo operator. If it is, we perform a bitwise OR operation with our running result.

Steps

• Initialize a variable result to 0.
• Iterate through each number num in the array nums.
• Check if num % 2 == 0.
• If true, update result using result = result | num (or result |= num).
• Return result after the loop finishes.

class Solution:
    def orOfEven(self, nums: list[int]) -> int:
        result = 0
        for num in nums:
            if num % 2 == 0:
                result |= num
        return result

Complexity

• Time: O(n), where n is the length of the array. We traverse the array once.
• Space: O(1). We only use a single variable to store the result.
• Notes: This is the most straightforward and efficient approach for this problem.

Approach 2: Functional Programming (Filter & Reduce)

Intuition We can use functional programming constructs to first filter the array to keep only even numbers, and then reduce the filtered array by applying the bitwise OR operation.

Steps

• Filter the array nums to create a new list containing only elements where num % 2 == 0.
• Apply a reduce operation on the filtered list with an initial value of 0 and the OR operator as the reducer function.
• Return the result. If the filtered list is empty, the reduce operation returns the initial value 0.

from functools import reduce

class Solution:
    def orOfEven(self, nums: list[int]) -> int:
        return reduce(lambda x, y: x | y, filter(lambda x: x % 2 == 0, nums), 0)

Complexity

• Time: O(n). We iterate through the array to filter and then to reduce.
• Space: O(n) in JavaScript/Python/Java due to the creation of a new filtered array or stream overhead. O(1) in C++ implementation shown (which effectively collapses to the iterative approach).
• Notes: While concise, this approach may use more memory than the iterative approach due to intermediate array creation in some languages.

Approach 3: Bitwise Check Optimization

Intuition Instead of using the modulo operator (%) to check for evenness, we can use bitwise AND. A number is even if its least significant bit is 0. We can check this using (num & 1) == 0. This is often slightly faster at the hardware level.

Steps

• Initialize result to 0.
• Iterate through each number num in nums.
• Check if (num & 1) == 0.
• If true, update result using result |= num.
• Return result.

class Solution:
    def orOfEven(self, nums: list[int]) -> int:
        result = 0
        for num in nums:
            if (num & 1) == 0:
                result |= num
        return result

Complexity

• Time: O(n). We traverse the array once.
• Space: O(1). We only use a single variable to store the result.
• Notes: This approach is functionally identical to the iterative simulation but uses bitwise operations for the condition check, which aligns well with the “Bit Manipulation” topic.