#2980

Easy

LeetCode Problem Workspace

Check if Bitwise OR Has Trailing Zeros

Check if a bitwise OR of two or more numbers has trailing zeros in its binary representation.

Problem Statement

You are given an array of positive integers nums. Your task is to determine if it is possible to select two or more elements from 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. You need to find out if it's possible to select two or more numbers whose bitwise OR has such a trailing zero.

Examples

Example 1

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

Output: true

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

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

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

Solution Approach

Check All Pair Combinations

Start by iterating through all possible pairs of numbers in the array. For each pair, perform a bitwise OR operation and check the binary representation to determine if it contains a trailing zero. If any valid pair is found, return true.

Bitwise OR with Pair Selection

You can optimize the process by limiting your checks to pairs of elements since, if a solution exists, a valid pair will always provide the answer. This reduces the complexity of the problem and speeds up the solution.

Early Termination on Success

Once a valid pair is found, terminate further checks and return the result immediately. This ensures efficiency, as further checks are unnecessary after finding a solution.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity for checking all pairs is O(n^2), where n is the length of the array. The space complexity is O(1) since no additional data structures are required beyond the array itself.

What Interviewers Usually Probe

Candidate demonstrates an understanding of bitwise operations and binary representation.
Candidate efficiently handles the problem by limiting the scope to pairs, avoiding unnecessary computations.
Candidate shows knowledge of early termination techniques to optimize performance.

Common Pitfalls or Variants

Common pitfalls

Not reducing the problem to only pairwise checks, which may lead to inefficiency.
Overcomplicating the problem by trying to handle larger sets than necessary.
Failing to check the binary representation properly for trailing zeros in the OR result.

Follow-up variants

Check if the bitwise AND of selected numbers has trailing zeros.
Check for a condition where the bitwise OR has multiple trailing zeros.
Find if there's any subset whose bitwise OR contains a trailing zero.

FAQ

What does the bitwise OR operation do in this problem?

In this problem, the bitwise OR operation combines the bits of two or more numbers and the task is to check if the result has trailing zeros in its binary representation.

How do I check if the bitwise OR has trailing zeros?

To check if the bitwise OR of two numbers has trailing zeros, convert the result to binary and inspect the least significant bits. If the binary number ends in '0', it has trailing zeros.

Why is it important to only check pairs of elements?

Since a valid solution always exists with a pair of elements if one exists, limiting the problem to pairs optimizes the solution by reducing unnecessary checks.

Can I optimize the solution further?

The solution is already quite efficient by checking pairs early and terminating as soon as a valid pair is found. Further optimization would focus on specific cases or constraints.

What is the time complexity of this problem?

The time complexity is O(n^2) because we check all pairs of elements in the array, where n is the number of elements.

terminal

Solution

Solution 1: Counting Even Numbers

According to the problem statement, if there are two or more elements in the array whose bitwise OR operation results in trailing zeros, then there must be at least two even numbers in the array. Therefore, we can count the number of even numbers in the array. If the count of even numbers is greater than or equal to $2$, then return `true`, otherwise return `false`.

1

2

3

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

Continue Practicing

#2997 minimum number of operations to make array xor equal to k #3011 find if array can be sorted #3022 minimize or of remaining elements using operations