# Check if Bitwise OR Has Trailing Zeros
**Difficulty:** EASY
[External](https://leetcode.com/problems/check-if-bitwise-or-has-trailing-zeros)
Canonical: https://scaleengineer.com/dsa/problems/check-if-bitwise-or-has-trailing-zeros
**Patterns:** [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation)
**Data structures:** Array
---
## Problem
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
## 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.
**Time:** 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:** 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:** 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.
### Explanation
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.

```java
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;
    }
}
```
### 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`.

## Optimal Single Pass Approach
This optimal approach is based on a key insight into the properties of bitwise operations. A number has a trailing zero in its binary representation if and only if it is even. The bitwise OR of a group of numbers will be even if and only if all numbers in that group are even. Therefore, the problem simplifies to checking if there are at least two even numbers in the input array.
**Time:** O(n), where `n` is the number of elements in the array. In the worst case, we traverse the entire array once. In the best case, we might find two even numbers at the beginning and terminate much earlier. · **Space:** O(1), as it only requires a single integer variable to keep count, using constant extra space.
**Pros:** Highly efficient with a linear time complexity.; Simple implementation once the core logic is understood.; Optimized to terminate early as soon as the condition is met.
**Cons:** The logic is not immediately obvious and requires understanding the properties of the bitwise OR operation.
### Explanation
The core logic is that for the bitwise OR of selected elements to have a trailing zero (i.e., be even), all selected elements must be even. If even a single selected element is odd, its least significant bit (LSB) is 1, which will make the LSB of the final OR result also 1, making the result odd.

So, the task reduces to finding if we can select two or more even numbers from the `nums` array. This is equivalent to checking if the array contains at least two even numbers. If it does, we can pick any two of them, and their bitwise OR will be even.

The algorithm iterates through the array just once, counting the number of even elements. To optimize, it can terminate as soon as the count reaches two, since that's all we need to confirm a `true` result.

```java
class Solution {
    public boolean hasTrailingZeros(int[] nums) {
        int evenCount = 0;
        for (int num : nums) {
            // Check if the number is even by checking its LSB
            if ((num & 1) == 0) {
                evenCount++;
            }
            // If we have found two even numbers, we can return true immediately
            if (evenCount >= 2) {
                return true;
            }
        }
        // If the loop completes and we haven't found at least two even numbers
        return false;
    }
}
```
### Algorithm
- Initialize a counter, `evenCount`, to 0.
- Iterate through each number `num` in the `nums` array.
- For each `num`, check if it is even. This can be done efficiently by checking if its least significant bit is 0 using `(num & 1) == 0`.
- If `num` is even, increment `evenCount`.
- After incrementing, if `evenCount` is equal to or greater than 2, it means we have found at least two even numbers. We can immediately stop and return `true`.
- If the loop finishes and `evenCount` is less than 2, it's impossible to select two or more even numbers. Return `false`.

# Solutions
### Java

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

```

### CPP

```cpp
class Solution {
public:
  bool hasTrailingZeros(vector<int> &nums) {
    int cnt = 0;
    for (int x : nums) {
      cnt += (x & 1 ^ 1);
    }
    return cnt >= 2;
  }
};

```

### Python

```python
class Solution:
    def hasTrailingZeros(
        self, nums: List[int]) -> bool: return sum(x & 1 ^ 1 for x in nums) >= 2

```