Watch 10 video solutions for Check if Bitwise OR Has Trailing Zeros, a easy level problem involving Array, Bit Manipulation. This walkthrough by Developer Docs has 463 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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] <= 100Problem 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 | 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 |