Check if Bitwise OR Has Trailing Zeros

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

You are given an array of positive integers nums. You have to check if it is possible to select two indices i and j such that i != j and the bitwise OR of the numbers at these indices has at least one trailing zero in its binary representation.

Return true if it is possible to select such indices, otherwise return false.

• Examples
• Constraints
• Brute Force
• Mathematical Optimization

Examples

Example 1:

Input: nums = [1,2,3,4,5]
Output: true
Explanation: Select i = 1 and j = 3. Their bitwise OR is 2 | 4 = 6, which has a trailing zero in binary (110).

Example 2:

Input: nums = [2,3,5,7]
Output: false
Explanation: No pair of indices results in a bitwise OR with a trailing zero.

Example 3:

Input: nums = [1,3,5,7]
Output: false
Explanation: No pair of indices results in a bitwise OR with a trailing zero.

Constraints

2 <= nums.length <= 100
1 <= nums[i] <= 10⁹

Brute Force

Intuition The most straightforward way to solve this problem is to check every possible pair of numbers in the array. For each pair, we calculate the bitwise OR and check if the result is even (has a trailing zero).

Steps

• Iterate through the array with index i from 0 to n-1.
• Iterate through the array with index j from i+1 to n-1.
• Calculate nums[i] | nums[j].
• If the result is even (modulo 2 equals 0), return true.
• If the loops finish without finding such a pair, return false.

class Solution:
    def hasTrailingZeros(self, nums: list[int]) -> bool:
        n = len(nums)
        for i in range(n):
            for j in range(i + 1, n):
                if (nums[i] | nums[j]) % 2 == 0:
                    return True
        return False

Complexity

• Time: O(n²)
• Space: O(1)
• Notes: This approach is simple but inefficient for large arrays, though acceptable given the constraint n <= 100.

Mathematical Optimization

Intuition A number has a trailing zero in binary if and only if it is even. The bitwise OR operation A | B results in an even number if and only if both A and B are even. If either A or B is odd, the least significant bit (LSB) of the result will be 1 (odd). Therefore, we simply need to check if there are at least two even numbers in the array.

Steps

• Initialize a counter for even numbers to 0.
• Iterate through each number in the array.
• If the number is even (modulo 2 equals 0), increment the counter.
• If the counter reaches 2, return true immediately.
• If the loop finishes, return false.

class Solution:
    def hasTrailingZeros(self, nums: list[int]) -> bool:
        count = 0
        for num in nums:
            if num % 2 == 0:
                count += 1
                if count >= 2:
                    return True
        return False

Complexity

• Time: O(n)
• Space: O(1)
• Notes: This is the optimal solution, reducing the time complexity to linear by leveraging mathematical properties of bitwise operations.