3688. Bitwise OR of Even Numbers in an Array
Problem Description
You are given an integer array nums.
Your task is to compute the bitwise OR of all the even numbers in the array and return the result.
In other words:
- Look at each number
xinnums. - Keep only the numbers that are even (i.e.,
x % 2 == 0). - Combine all of these even numbers using the bitwise OR operation (
|). - Return the final combined value.
If the array contains no even numbers at all, simply return 0.
For example, if nums = [1, 2, 3, 4, 5, 6], the even numbers are 2, 4, and 6. The answer would be 2 | 4 | 6 = 6.
How We Pick the Algorithm
Why Simulation / Basic DSA?
This problem maps to Simulation / Basic DSA through a short path in the full flowchart.
The problem filters even numbers and computes their bitwise OR by straightforward iteration with an accumulator.
Open in FlowchartIntuition
The problem directly tells us what to do: pick out the even numbers and OR them together. So the most natural idea is a straightforward simulation — just do exactly what the problem says, step by step.
Two small observations make this easy:
-
Checking for even numbers is simple: a number
xis even whenx % 2 == 0(equivalently, its lowest bit is0, sox & 1 == 0). -
Bitwise OR has a perfect "starting value": since
0 | x = xfor anyx, we can initialize an accumulatorans = 0and OR each even number into it. This also elegantly handles the edge case — if there are no even numbers,ansis never updated and stays0, which is exactly what the problem asks us to return.
Because OR is associative and commutative, the order in which we combine the even numbers doesn't matter, so a single left-to-right pass through the array is enough. There's no need for sorting, extra data structures, or any clever tricks — one linear scan with an accumulator solves it.
Solution Approach
Simulation
We follow the problem statement directly using a single pass over the array:
-
Initialize an accumulator: define a variable
answith an initial value of0. Since0 | x = x, this starting value does not affect the result, and it also serves as the correct answer when no even numbers exist. -
Iterate and filter: go through each element
xinnums. For eachx, check whether it is even usingx % 2 == 0. -
Accumulate with OR: if
xis even, update the accumulator withans = ans | x. -
Return the result: after the loop finishes,
ansholds the bitwise OR of all even numbers, so we return it.
Implementation Details
The Python solution expresses this loop compactly in one line:
class Solution:
def evenNumberBitwiseORs(self, nums: List[int]) -> int:
return reduce(or_, (x for x in nums if x % 2 == 0), 0)
- The generator expression
(x for x in nums if x % 2 == 0)lazily produces only the even numbers, handling the filter step without building an extra list. reduce(or_, ..., 0)folds these values together using the bitwise OR operator (or_from theoperatormodule), starting from the initial value0. This handles both the accumulate step and the empty-case fallback in one call.
This is functionally identical to the explicit loop:
ans = 0 for x in nums: if x % 2 == 0: ans |= x return ans
Complexity Analysis
- Time complexity:
O(n), wherenis the length ofnums— each element is visited exactly once with constant work per element. - Space complexity:
O(1)— only a single accumulator variable is used; the generator does not materialize any intermediate collection.
Example Walkthrough
Let's trace the algorithm on a small input: nums = [3, 2, 9, 12, 7, 5].
We initialize the accumulator ans = 0 and scan the array from left to right, checking each element for evenness:
| Step | x | Even? (x % 2 == 0) | Operation | ans (binary) | ans (decimal) |
|---|---|---|---|---|---|
| — | — | — | initialize | 0000 | 0 |
| 1 | 3 | No | skip | 0000 | 0 |
| 2 | 2 | Yes | 0 | 2 | 0010 | 2 |
| 3 | 9 | No | skip | 0010 | 2 |
| 4 | 12 | Yes | 2 | 12 | 1110 | 14 |
| 5 | 7 | No | skip | 1110 | 14 |
| 6 | 5 | No | skip | 1110 | 14 |
Breaking down the key OR step (Step 4) at the bit level:
2 = 0010 12 = 1100 ---- OR 14 = 1110
The OR operation keeps every bit that appears in at least one of the even numbers, so the set bits of 2 (0010) and 12 (1100) merge into 1110, which is 14.
After the loop finishes, we return ans = 14.
Edge case check: if the input were nums = [1, 3, 5], no element passes the evenness test, so ans is never updated and the initial value 0 is returned — exactly what the problem requires, with no special-case code needed.
Solution Implementation
1from functools import reduce
2from operator import or_
3from typing import List
4
5
6class Solution:
7 def evenNumberBitwiseORs(self, nums: List[int]) -> int:
8 # Filter out the even numbers from the input list,
9 # then combine them with the bitwise OR operation.
10 # The initial value 0 ensures a valid result (0) even
11 # when the list contains no even numbers, since
12 # 0 OR x == x for any integer x.
13 return reduce(or_, (num for num in nums if num % 2 == 0), 0)
14```
15
16**Explanation of the approach:**
17
181. **Filtering**: The generator expression `(num for num in nums if num % 2 == 0)` lazily yields only the even numbers, avoiding the creation of an intermediate list.
192. **Aggregation**: `reduce(or_, ..., 0)` folds the bitwise OR (`or_` from the `operator` module) across all filtered values.
203. **Initial value**: Passing `0` as the third argument to `reduce` handles the edge case where no even numbers exist — the result is simply `0`, and it doesn't affect the outcome otherwise because `0` is the identity element for bitwise OR.
21
22**Alternative iterative version** (same logic, no functional helpers):
23
24```python3
25from typing import List
26
27
28class Solution:
29 def evenNumberBitwiseORs(self, nums: List[int]) -> int:
30 # Accumulate the bitwise OR of all even numbers.
31 result = 0
32 for num in nums:
33 if num % 2 == 0: # Keep only even numbers
34 result |= num # Merge bits via bitwise OR
35 return result
361class Solution {
2 /**
3 * Computes the bitwise OR of all even numbers in the given array.
4 *
5 * @param nums the input array of integers
6 * @return the bitwise OR of all even elements; 0 if no even element exists
7 */
8 public int evenNumberBitwiseORs(int[] nums) {
9 // Accumulator for the bitwise OR result, initialized to 0
10 // (0 is the identity element for the OR operation)
11 int result = 0;
12
13 // Iterate over each number in the array
14 for (int num : nums) {
15 // Check whether the current number is even
16 if (num % 2 == 0) {
17 // Merge the even number into the result using bitwise OR
18 result |= num;
19 }
20 }
21
22 // Return the accumulated bitwise OR of all even numbers
23 return result;
24 }
25}
261class Solution {
2public:
3 int evenNumberBitwiseORs(vector<int>& nums) {
4 // Initialize the result to 0, which is the identity element for bitwise OR
5 int result = 0;
6
7 // Iterate over each number in the input array
8 for (int num : nums) {
9 // Check whether the current number is even
10 if (num % 2 == 0) {
11 // Accumulate the even number into the result using bitwise OR
12 result |= num;
13 }
14 }
15
16 // Return the bitwise OR of all even numbers in the array
17 return result;
18 }
19};
201/**
2 * Computes the bitwise OR of all even numbers in the given array.
3 *
4 * Approach:
5 * 1. Iterate through the array using `reduce`, starting with an accumulator of 0.
6 * 2. For each element, check whether it is even (divisible by 2).
7 * 3. If even, merge it into the accumulator using the bitwise OR operator.
8 * 4. If odd, skip it and keep the accumulator unchanged.
9 *
10 * Time Complexity: O(n), where n is the length of the array (single pass).
11 * Space Complexity: O(1), only a constant amount of extra space is used.
12 *
13 * @param nums - The input array of integers.
14 * @returns The bitwise OR of all even numbers; returns 0 if no even number exists.
15 */
16function evenNumberBitwiseORs(nums: number[]): number {
17 return nums.reduce(
18 (ans: number, num: number): number =>
19 // Include `num` in the result only when it is even
20 num % 2 === 0 ? ans | num : ans,
21 0 // Initial accumulator value (identity element for bitwise OR)
22 );
23}
24```
25
26**Explanation of the changes:**
27
281. **Naming standardization**: The loop variable `x` was renamed to `num`, which more clearly conveys that it represents a numeric element from the input array. The function name `evenNumberBitwiseORs` is preserved as required.
29
302. **Explicit type annotations**: Added types to the `reduce` callback parameters and return value (`ans: number, num: number): number`) to make full use of TypeScript's type system.
31
323. **Comments added**: A JSDoc block documents the purpose, approach, complexity, parameters, and return value, while inline comments clarify the even-number check and the initial accumulator.
33
34**Alternative perspective** — if you prefer an imperative style, the same logic can be written with a simple loop, which some find easier to read and debug:
35
36```typescript
37function evenNumberBitwiseORs(nums: number[]): number {
38 let ans = 0;
39 for (const num of nums) {
40 if (num % 2 === 0) {
41 ans |= num; // Accumulate even numbers via bitwise OR
42 }
43 }
44 return ans;
45}
46Time and Space Complexity
-
Time complexity:
O(n), wherenis the length of the arraynums. The code iterates through every element ofnumsexactly once via the generator expression(x for x in nums if x % 2 == 0), performing a constant-time parity checkx % 2 == 0and a constant-time bitwise OR operationor_for each element during thereduceaggregation. -
Space complexity:
O(1). The generator expression evaluates elements lazily without materializing an intermediate list, andreducemaintains only a single accumulator value. Therefore, the extra space used does not grow with the input size.
Pattern Learn more about how to find time and space complexity quickly.
Common Pitfalls
1. Confusing logical or with bitwise | (or operator.or_)
A frequent mistake in Python is writing the logical keyword or where the bitwise operator is required:
# WRONG: `or` is logical, not bitwise result = 0 for num in nums: if num % 2 == 0: result = result or num # returns the first "truthy" value!
With nums = [2, 4, 6], this returns 2 instead of 2 | 4 | 6 = 6, because result or num short-circuits and keeps the first non-zero operand rather than merging bits. The same confusion can occur when reaching for operator.or_ vs. a hand-written lambda — or_ is the bitwise version (a | b), but lambda a, b: a or b is not.
Fix: always use | / |= (or operator.or_ with reduce):
result |= num
2. Forgetting the initializer in reduce, crashing on "no even numbers"
# WRONG: raises TypeError when the generator is empty return reduce(or_, (x for x in nums if x % 2 == 0))
If nums contains no even numbers (e.g., nums = [1, 3, 5]), the generator yields nothing and reduce with no initial value raises:
TypeError: reduce() of empty iterable with no initial value
Fix: pass 0 as the third argument. Since 0 is the identity element for bitwise OR (0 | x == x), it is both safe for the general case and the correct answer for the empty case:
return reduce(or_, (x for x in nums if x % 2 == 0), 0)
3. Checking evenness with num % 2 == 1 logic ported from other languages
A subtle trap when handling potential negative inputs: testing for odd via num % 2 == 1 and inverting the condition works in Python (where -4 % 2 == 0 and -3 % 2 == 1), but the equivalent C++/Java code num % 2 == 1 fails for negative odd numbers because -3 % 2 == -1 in those languages. Translating such code back and forth often introduces bugs.
Fix: test evenness directly and robustly in any language:
if num % 2 == 0: # works for negatives in Python
or use the bit trick, which is language-agnostic:
if num & 1 == 0: # last bit is 0 ⇒ even
4. Initializing the accumulator with nums[0] unconditionally
Copying the common "fold" pattern of seeding the accumulator with the first element is wrong here:
# WRONG: nums[0] may be odd and must not participate in the OR result = nums[0] for num in nums[1:]: ...
If nums[0] is odd (e.g., nums = [1, 2, 4]), its bits pollute the result (1 | 2 | 4 = 7 instead of 6).
Fix: start from 0, the OR identity, so only filtered (even) values ever contribute:
result = 0
Ready to land your dream job?
Unlock your dream job with a 5-minute quiz for a personalized study roadmap!
Get My RoadmapIs the following code DFS or BFS?
void search(Node root) { if (!root) return; visit(root); root.visited = true; for (Node node in root.adjacent) { if (!node.visited) { search(node); } } }
Recommended Readings
Coding Interview Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way
Recursion If you prefer videos here's a video that explains recursion in a fun and easy way Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https assets algo monster recursion jpg You first call Ben and ask him
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity describes how the time needed
Want a Structured Path to Master System Design Too? Don’t Miss This!