LeetCode 3688 - Bitwise OR of Even Numbers in an Array

LeetCode Problem 3688

Difficulty: 🟢 Easy
Topics: Array, Bit Manipulation, Simulation

Solution

Problem Understanding

This problem asks us to compute the bitwise OR of all even numbers in a given integer array nums. A number is considered even if it is divisible by 2, meaning its least significant bit is 0. The task is to iterate through the array, select only the even numbers, and combine them using the bitwise OR operation.

The input is a list of integers nums with length between 1 and 100, and each element is in the range 1 to 100. Because of these constraints, the input size is small, and a linear scan solution will be sufficient.

The expected output is a single integer representing the cumulative OR of all even numbers. If there are no even numbers in the array, the result must be 0.

The constraints imply that performance is not a concern beyond linear time. This means clarity and correctness are more important than optimization.

Important edge cases include an array with no even numbers, an array where all numbers are even, an array with a single element, and an array where even numbers include powers of two or repeated values. Another subtle case is when all even numbers are zero, although the constraints guarantee nums[i] >= 1, so zero does not occur.

Approaches

The brute-force approach conceptually considers every element and performs repeated OR operations across all even numbers, possibly building a separate filtered list first and then iterating over it again to compute the OR. While this is still linear in practice, it is less direct because it introduces unnecessary intermediate storage or repeated passes over the data.

The optimal approach observes that bitwise OR is both associative and commutative, meaning the order does not matter and we can accumulate the result in a single pass. We simply traverse the array once, check if each number is even using num % 2 == 0 or (num & 1) == 0, and OR it into a running accumulator.

The key insight is that we do not need to store even numbers separately or revisit the array. Each even number can immediately contribute to the final result.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n)	O(n)	Filter even numbers first, then compute OR in a second pass
Optimal	O(n)	O(1)	Single pass accumulation of OR over even numbers

Algorithm Walkthrough

1. Initialize a variable result to 0, which will store the cumulative bitwise OR of all even numbers. This starts at 0 because OR-ing with 0 does not affect any bits.
2. Iterate through each element num in the input array nums. We process one number at a time to maintain a single-pass solution.
3. For each number, check whether it is even. This is done by verifying if the remainder when divided by 2 is zero, or equivalently if the least significant bit is 0 using a bitwise AND operation.
4. If the number is even, update result by performing a bitwise OR between result and the current number. This step accumulates all set bits across even numbers.
5. If the number is odd, ignore it and continue to the next element since it does not contribute to the final result.
6. After processing all elements, return result as the final answer.

Why it works: the correctness relies on the associative and commutative properties of the bitwise OR operation. Since OR combines bits independently and does not depend on ordering, accumulating even numbers in a single running variable guarantees that all set bits present in any even number are preserved in the final result.

Python Solution

from typing import List

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

The implementation maintains a single accumulator result. It iterates through the list once, checks each number for evenness using num % 2 == 0, and updates the accumulator using the |= operator. If a number is odd, it is skipped. The final accumulator is returned after the loop completes.

Go Solution

func evenNumberBitwiseORs(nums []int) int {
    result := 0

    for _, num := range nums {
        if num%2 == 0 {
            result |= num
        }
    }

    return result
}

In Go, the logic is identical to Python. We use a range loop to iterate over the slice, and maintain an integer accumulator. The bitwise OR assignment operator |= is used in the same way. There are no special considerations for overflow because the values are small (up to 100), and Go integers easily handle this range.

Worked Examples

Example 1: nums = [1,2,3,4,5,6]

We track result step by step.

Step	num	Even?	result before	result after
1	1	No	0	0
2	2	Yes	0	2
3	3	No	2	2
4	4	Yes	2	6
5	5	No	6	6
6	6	Yes	6	6

Final output is 6.

Example 2: nums = [7,9,11]

No numbers are even, so result remains 0 throughout.

Final output is 0.

Example 3: nums = [1,8,16]

Step	num	Even?	result before	result after
1	1	No	0	0
2	8	Yes	0	8
3	16	Yes	8	24

Final output is 24.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each element is processed exactly once in a single pass
Space	O(1)	Only a constant number of variables are used

The solution is optimal because it requires only one traversal of the input array and maintains a constant-size accumulator regardless of input size.

Test Cases

assert Solution().evenNumberBitwiseORs([1,2,3,4,5,6]) == 6  # mixed even and odd numbers
assert Solution().evenNumberBitwiseORs([7,9,11]) == 0       # no even numbers
assert Solution().evenNumberBitwiseORs([1,8,16]) == 24      # powers of two
assert Solution().evenNumberBitwiseORs([2]) == 2            # single even element
assert Solution().evenNumberBitwiseORs([3]) == 0            # single odd element
assert Solution().evenNumberBitwiseORs([2,2,2]) == 2        # duplicates
assert Solution().evenNumberBitwiseORs([2,4,8,16]) == 30    # all evens
assert Solution().evenNumberBitwiseORs([1]) == 0            # smallest input odd

Test	Why
[1,2,3,4,5,6]	Standard mixed parity case
[7,9,11]	Validates all-odd behavior
[1,8,16]	Validates OR growth across powers of two
[2]	Single-element even case
[3]	Single-element odd case
[2,2,2]	Duplicate values do not change result
[2,4,8,16]	All even numbers case
[1]	Minimal input size edge case

Edge Cases

One important edge case is when there are no even numbers in the array. In this situation, the algorithm never updates the accumulator and correctly returns the initialized value of 0. This works naturally because 0 is the identity element for bitwise OR.

Another edge case is when the array contains only one element. If that element is even, the result should be the element itself; if it is odd, the result should be 0. The single-pass logic handles both cases without modification because each element is independently evaluated.

A third edge case involves repeated even numbers. Since bitwise OR is idempotent for identical values (x | x = x), duplicates do not change the result. The accumulator remains correct regardless of repetition, and no special handling is needed.

A final consideration is that all numbers are positive and small, so there are no concerns about negative bit representations or integer overflow in either Python or Go implementations.