Check if Bitwise OR Has Trailing Zeros

EASY

Description

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 <= 100
1 <= nums[i] <= 100

Approaches

Checkout 2 different approaches to solve Check if Bitwise OR Has Trailing Zeros. Click on different approaches to view the approach and algorithm in detail.

Brute-Force Approach by Checking All Pairs

This approach directly translates the problem statement into code by checking every possible pair of elements in the array. For each pair, it computes their bitwise OR and checks if the result has a trailing zero. While straightforward, it is not the most efficient way to solve the problem.

Algorithm

Iterate through the array with an index i from 0 to n-2, where n is the length of the array.
Inside this loop, iterate with a second index j from i+1 to n-1.
For each pair of elements (nums[i], nums[j]), calculate their bitwise OR: orResult = nums[i] | nums[j].
Check if the orResult has a trailing zero. This is equivalent to checking if orResult is an even number. A simple way to do this is to check if its least significant bit is 0 using the expression (orResult & 1) == 0.
If the condition is met, it means we have found a valid selection of two elements. Return true immediately.
If the loops complete without finding any such pair, it means no selection of two or more elements can produce an OR with a trailing zero. Return false.

The fundamental idea is to test all combinations of two elements. If we can find any pair (a, b) from the array such that a | b has a trailing zero, we have satisfied the condition. A number has a trailing zero in its binary representation if and only if it is an even number. Therefore, we are looking for a pair (nums[i], nums[j]) such that nums[i] | nums[j] is even.

The algorithm uses two nested loops to generate all unique pairs of indices (i, j). For each pair, it performs the bitwise OR operation and then checks the least significant bit of the result. The bitwise AND operation result & 1 is an efficient way to get the least significant bit. If this bit is 0, the number is even, and we have found our answer.

class Solution {
    public boolean hasTrailingZeros(int[] nums) {
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                // Calculate the bitwise OR of the pair
                int orResult = nums[i] | nums[j];
                // Check if the last bit is 0 (i.e., the number is even)
                if ((orResult & 1) == 0) {
                    return true;
                }
            }
        }
        return false;
    }
}

Complexity Analysis

Time Complexity: O(n^2), where `n` is the number of elements in the `nums` array. This is because of the nested loops that iterate through all unique pairs of elements.Space Complexity: O(1), as it only uses a constant amount of extra space for loop variables and the OR result, regardless of the input size.

Pros and Cons

Pros:

Simple to understand and implement directly from the problem description.
Correctly solves the problem for the given constraints.

Cons:

Inefficient for large arrays. The time complexity is quadratic, which can be slow if the input array size is large.

Code Solutions

Checking out 3 solutions in different languages for Check if Bitwise OR Has Trailing Zeros. Click on different languages to view the code.

class Solution {
public
  boolean hasTrailingZeros(int[] nums) {
    int cnt = 0;
    for (int x : nums) {
      cnt += (x & 1 ^ 1);
    }
    return cnt >= 2;
  }
}

Video Solution

Watch the video walkthrough for Check if Bitwise OR Has Trailing Zeros

Patterns:

Bit Manipulation

Data Structures:

Array