LeetCode 2980 - Check if Bitwise OR Has Trailing Zeros

The problem asks us to determine whether we can select two or more elements from a given array of positive integers such that their bitwise OR produces a number whose binary representation ends with at least one zero.

leetcodeeasyarraybit-manipulation

LeetCode Problem 2980

Difficulty: 🟢 Easy
Topics: Array, Bit Manipulation

Solution

Problem Understanding

The problem asks us to determine whether we can select two or more elements from a given array of positive integers such that their bitwise OR produces a number whose binary representation ends with at least one zero. In other words, the least significant bit of the OR result should be 0.

The input is an array nums of length between 2 and 100, where each element is a positive integer between 1 and 100. These constraints are small, meaning an $O(n^2)$ approach could be feasible, but the key is to recognize patterns in binary trailing zeros to optimize.

A trailing zero in binary corresponds to the number being even. Therefore, we are essentially looking for two numbers whose OR is even. This translates to at least one selected number having its least significant bit as 0.

Edge cases include arrays with all odd numbers, which can never produce an even OR result, arrays with duplicates, and arrays where the smallest numbers already create a trailing zero.

Approaches

Brute Force Approach

A naive approach is to try every possible subset of size 2 or more, compute the OR of that subset, and check if the result is even. This is correct because it exhaustively checks all possibilities, but it is inefficient. The number of subsets of size ≥2 grows exponentially with the number of elements. For n = 100, this is clearly infeasible.

Optimal Approach

The key observation is that a number has a trailing zero if and only if it is even. Furthermore, the bitwise OR of multiple numbers is even if and only if at least one of them is even. Therefore, we only need to check if there are at least two even numbers, or one even number plus any other number, to satisfy the condition.

Specifically:

  • If there is any even number, we can pair it with any other number, producing an OR result that is even.
  • If all numbers are odd, the OR of any subset will also be odd, hence cannot have trailing zeros.

This reduces the problem to a simple scan to check for at least one even number and ensure there are at least two elements in total.

Approach Time Complexity Space Complexity Notes
Brute Force O(2^n) O(1) Check all subsets of size ≥2 and compute OR
Optimal O(n) O(1) Scan for at least one even number, return true if found

Algorithm Walkthrough

  1. Initialize a counter or flag to track whether an even number exists.
  2. Iterate through the array nums.
  3. For each element, check if it is even (num % 2 == 0).
  4. If an even number is found, immediately return true because pairing it with any other number yields a valid OR with trailing zeros.
  5. If the loop ends and no even numbers are found, return false since all numbers are odd and their OR cannot produce a trailing zero.

Why it works: This approach relies on the invariant that the OR of numbers is even if at least one number is even. Checking the presence of at least one even number is sufficient because any subset containing that even number and any other element guarantees the OR will have a trailing zero.

Python Solution

from typing import List

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

The implementation iterates through the list. The moment it finds an even number, it returns True, which directly corresponds to the algorithm’s step of pairing any even number with another number. If no even number exists, the function returns False.

Go Solution

func hasTrailingZeros(nums []int) bool {
    for _, num := range nums {
        if num%2 == 0 {
            return true
        }
    }
    return false
}

In Go, we iterate over the slice nums using a range loop. The modulo operation % determines even numbers. Returning true immediately on the first even number optimizes the solution similarly to the Python version.

Worked Examples

Example 1: nums = [1, 2, 3, 4, 5]

Scan finds 2 as the first even number, immediately returning true.

Iteration num num%2==0 Action
1 1 false continue
2 2 true return True

Example 2: nums = [2, 4, 8, 16]

Scan finds 2 as even, return true. Any subset including 2 will produce OR with trailing zeros.

Example 3: nums = [1, 3, 5, 7, 9]

All numbers are odd, no even number found, return false.

Complexity Analysis

Measure Complexity Explanation
Time O(n) We iterate through the array once to check for an even number
Space O(1) Constant extra space, only a few variables used

The reasoning is straightforward: a single pass through the array suffices, and no additional data structures are required.

Test Cases

# Provided examples
assert Solution().hasTrailingZeros([1,2,3,4,5]) == True  # Example 1
assert Solution().hasTrailingZeros([2,4,8,16]) == True   # Example 2
assert Solution().hasTrailingZeros([1,3,5,7,9]) == False # Example 3

# Edge cases
assert Solution().hasTrailingZeros([2,3]) == True        # Minimum input size, contains even
assert Solution().hasTrailingZeros([1,1]) == False       # Minimum input size, all odd
assert Solution().hasTrailingZeros([100]*100) == True    # All even numbers
assert Solution().hasTrailingZeros([1]*100) == False     # All odd numbers
assert Solution().hasTrailingZeros([1,2]) == True        # Smallest even + odd pair
Test Why
[1,2,3,4,5] Standard mixed array, OR with trailing zeros exists
[2,4,8,16] All even numbers, trivially true
[1,3,5,7,9] All odd numbers, cannot have trailing zeros
[2,3] Minimum array size with an even number
[1,1] Minimum array size, all odd, should return false
[100]*100 Large array, all even numbers
[1]*100 Large array, all odd numbers
[1,2] Smallest array with exactly one even

Edge Cases

One important edge case is when all numbers are odd, which will always return false. A naive implementation that attempts to OR all combinations could waste time and incorrectly assume some odd numbers might produce trailing zeros, but the algorithm correctly handles this by checking parity.

Another edge case is arrays of size 2, the minimum allowed. The implementation works correctly even in this scenario, immediately checking both elements.

Finally, arrays with duplicate numbers do not affect correctness. For example, multiple copies of an even number immediately satisfy the condition, and the algorithm does not need to deduplicate elements because a single even number is enough.