Check if Bitwise OR Has Trailing Zeros - Solution & Explanation
Problem Statement
You are given an array of positive integers nums.
You have to check if it is possible to select two or more elements in the array such that the bitwise OR of the selected elements has at least one trailing zero in its binary representation.
For example, the binary representation of 5, which is "101", does not have any trailing zeros, whereas the binary representation of 4, which is "100", has two trailing zeros.
Return true if it is possible to select two or more elements whose bitwise OR has trailing zeros, return false otherwise.
Example 1:
Input: nums = [1,2,3,4,5] Output: true Explanation: If we select the elements 2 and 4, their bitwise OR is 6, which has the binary representation "110" with one trailing zero.
Example 2:
Input: nums = [2,4,8,16] Output: true Explanation: If we select the elements 2 and 4, their bitwise OR is 6, which has the binary representation "110" with one trailing zero. Other possible ways to select elements to have trailing zeroes in the binary representation of their bitwise OR are: (2, 8), (2, 16), (4, 8), (4, 16), (8, 16), (2, 4, 8), (2, 4, 16), (2, 8, 16), (4, 8, 16), and (2, 4, 8, 16).
Example 3:
Input: nums = [1,3,5,7,9] Output: false Explanation: There is no possible way to select two or more elements to have trailing zeros in the binary representation of their bitwise OR.
Constraints:
2 <= nums.length <= 1001 <= nums[i] <= 100
Approach Overview
Problem Overview: You are given an integer array and must determine whether there exists a pair of elements whose bitwise OR ends with a trailing zero in binary. A trailing zero means the least significant bit (LSB) of the result is 0. The key observation is that a bitwise OR only produces a 0 in the last bit if both numbers already have 0 there.
Approach 1: Check Pairs for Trailing Zeros (O(n²) time, O(1) space)
The direct approach checks every pair of numbers in the array. For each pair (nums[i], nums[j]), compute nums[i] | nums[j] and test whether the result has a trailing zero. You can verify this with a bit check like ((nums[i] | nums[j]) & 1) == 0. This works because the least significant bit determines whether a number is even or odd. The algorithm iterates through all n(n−1)/2 pairs, which makes the time complexity O(n²), while only constant extra memory is used. This approach clearly demonstrates the property of the OR operation but becomes inefficient for large arrays.
Approach 2: Check Individual Elements for Trailing Zeros (O(n) time, O(1) space)
A more efficient solution comes from analyzing the bit behavior. For a | b to end with 0, both a and b must have their least significant bit equal to 0. In other words, both numbers must be even. Instead of evaluating pairs, scan the array once and count how many numbers are even. As soon as you find at least two even numbers, you know their OR will also be even and therefore contain a trailing zero. The scan requires a single pass with a simple bit check like (num & 1) == 0. This reduces the runtime to O(n) with O(1) space.
This optimization relies on understanding how bitwise operations behave at the bit level. The least significant bit controls parity, and the OR operator only outputs 0 when both inputs have 0. Recognizing this removes the need for pairwise comparisons entirely. Problems like this frequently appear in bit manipulation practice because they reward pattern recognition rather than brute force enumeration.
Recommended for interviews: Start by explaining the pair-checking method to demonstrate correctness and understanding of the OR operation. Then derive the optimized approach by analyzing the least significant bit and parity of numbers. Interviewers typically expect the O(n) scan because it shows you understand binary properties instead of relying on brute force. This pattern appears often in problems involving arrays and bitwise operations.
Approach 1: Approach 1: Check Pairs for Trailing Zeros
In this approach, we will iterate through all possible pairs of elements in the array and check if their bitwise OR results in a number that has at least one trailing zero in its binary representation. We can check for trailing zeros using the condition (num & 1) == 0 for any integer num.
In this C implementation, we define a helper function hasTrailingZero to check if a number has trailing zeros. We check every possible pair of elements in the array, compute their bitwise OR, and use the helper function to determine if the result has trailing zeros. If such a pair is found, it returns true; otherwise, it returns false.
Complexity
The time complexity is O(n^2) since we are checking each pair, and the space complexity is O(1) because we are only using a constant amount of extra space.
Approach 2: Approach 2: Check Individual Elements for Trailing Zeros
If any single number in the array has a trailing zero, then selecting any two or more numbers that include it would definitely have trailing zeros in their OR result. Hence, just a single check over each number's binary representation is required.
In this C implementation, we iterate over each element of the array and check if it has a trailing zero using the hasTrailingZero function. If any one element has one, we return true.
Complexity
The time complexity is O(n) as we traverse each element once, and space complexity is O(1).
Approach 3: Counting Even Numbers
According to the problem statement, if there are two or more elements in the array whose bitwise OR operation results in trailing zeros, then there must be at least two even numbers in the array. Therefore, we can count the number of even numbers in the array. If the count of even numbers is greater than or equal to 2, then return true, otherwise return false.
The time complexity is O(n), where n is the length of the array. The space complexity is O(1).
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Approach 1: Check Pairs for Trailing Zeros | The time complexity is |
| Approach 2: Check Individual Elements for Trailing Zeros | The time complexity is |
| Counting Even Numbers | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Check All Pairs with Bitwise OR | O(n²) | O(1) | Good for explaining brute force logic or when constraints are very small |
| Count Even Numbers (Bit Check) | O(n) | O(1) | Optimal approach; uses parity insight to avoid pair comparisons |
Video Solution
Leetcode | 2980. Check if Bitwise OR Has Trailing Zeros | Easy | Java Solution • Developer Docs • 511 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Check if Bitwise OR Has Trailing Zeros easy or hard?
Check if Bitwise OR Has Trailing Zeros Python/Java solution
How to solve Check if Bitwise OR Has Trailing Zeros in O(n)?
What is the best approach for Check if Bitwise OR Has Trailing Zeros?
Is Check if Bitwise OR Has Trailing Zeros asked at Google/Amazon/Meta?
What data structure is used in Check if Bitwise OR Has Trailing Zeros?
What is the time complexity of Check if Bitwise OR Has Trailing Zeros?
Ready to solve this problem?
Practice Check if Bitwise OR Has Trailing Zeros with our built-in code editor and test cases.
Practice on FleetCode