We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Check if Bitwise OR Has Trailing Zeros

Number: 3246

Difficulty: Easy

Paid? No

Companies: Meituan

Problem Description

Given an array of positive integers, determine if it is possible to select two or more elements such that the bitwise OR of the selected elements has at least one trailing zero in its binary representation. Essentially, we want the final bitwise OR result to be even.

Key Insights

  • A number has at least one trailing zero if and only if it is even (i.e., its least significant bit is 0).
  • Bitwise OR of numbers is even only if none of the selected numbers contribute a 1 in the least significant bit; thus, all numbers in the selection must be even.
  • Since the selection must contain at least two numbers, we simply need to check if there are at least two even numbers in the array.

Space and Time Complexity

Time Complexity: O(n), where n is the number of elements in the input array, because we need to scan the array once. Space Complexity: O(1), as we only use a counter variable to track even numbers.

Solution

The approach is straightforward. We iterate through the array and count how many even numbers there are. If we find at least two even numbers, then we can select those two and their bitwise OR will be even (thus having at least one trailing zero in its binary representation). Otherwise, if there are fewer than two even numbers, it is impossible to meet the requirement, so the answer is false.

Code Solutions

# Function to check if there exists a selection of at least two numbers whose
# bitwise OR has at least one trailing zero (i.e., is even)
def has_trailing_zero(nums):
    # Counter for even numbers
    even_count = 0
    # Iterate through each number in the array
    for num in nums:
        # Check if the number is even (LSB equals 0)
        if num % 2 == 0:
            even_count += 1
        # Early return: if we found at least two evens, we meet the condition
        if even_count >= 2:
            return True
    # If less than two even numbers are found, condition is not met
    return False

# Example usage
print(has_trailing_zero([1,2,3,4,5]))  # Expected output: True
print(has_trailing_zero([1,3,5,7,9]))  # Expected output: False
← Back to All Questions