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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Check if Bitwise OR Has Trailing Zeros

Difficulty: Easy

Problem 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. Return true if it is possible, otherwise return false.

Key Insights

  • The bitwise OR operation between two numbers results in a number that has a binary representation where a bit is set if it is set in either operand.
  • A number has a trailing zero in its binary representation if it is even (i.e., it ends with a '0').
  • To have a trailing zero in the bitwise OR of two or more numbers, at least one of the selected numbers must be even.
  • If all selected numbers are odd, their bitwise OR will also be odd and will not have trailing zeros.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Solution

To solve this problem, we can iterate through the array and check if there are at least two even numbers. If we find at least two even numbers, we can conclude that their bitwise OR will have at least one trailing zero. If not, it is impossible to get a trailing zero in the OR result.

Code Solutions

def has_trailing_zeros(nums):
    even_count = 0  # Counter for even numbers
    for num in nums:
        if num % 2 == 0:  # Check if the number is even
            even_count += 1
        if even_count >= 2:  # If we found at least two even numbers
            return True
    return False  # Not enough even numbers found
← Back to All Questions