2980. Check if Bitwise OR Has Trailing Zeros

EasyBit ManipulationArray

Problem Description

This LeetCode problem requires us to look at an array of positive integers and determine whether we can select two or more elements from this array such that the binary representation of their bitwise OR (|) operation ends with at least one trailing zero. A trailing zero in this context means that the least significant bit (rightmost bit) in the binary representation is a 0. For instance, if we take the binary representation of 4 which is "100", it clearly has two trailing zeros. This contrasts with the number 5 whose binary representation is "101", with no trailing zeros because the last bit is a 1.

The essential challenge here is to check the given array and return true if such a selection is possible and return false otherwise.

Intuition

The intuition behind the solution can be drawn directly from the nature of the bitwise OR operation and the structure of binary numbers. When we perform a bitwise OR between two numbers, each bit in the result is a 1 if any of the corresponding bits of the operands is a 1. This implies that if we have a trailing zero in the result, both operands must have a zero in the corresponding least significant bit position.

Now, focusing on even and odd numbers, we know that in binary, an even number always ends with a 0, and an odd number always ends with a 1. Therefore, when we OR an even number with another even number, the result will also end with a 0, because both numbers have a 0 at the least significant bit. However, if we OR an odd number (ending in 1) with any other number, the result will always end with a 1, thus not having a trailing zero.

From here, we can deduce that if we have at least two even numbers in the array, we can definitely perform a bitwise OR operation between them that results in at least one trailing zero. Hence, our solution approach is to count the number of even numbers in the array. If the count is two or more, our function can confidently return true, signaling that it's possible to select elements that meet the problem's requirement; otherwise, it will return false.

Solution Approach

The approach to the solution is straightforward, employing a simple counting strategy without the need for any complex data structures or algorithms. The algorithms or patterns used in this solution utilize basic arithmetic and bitwise operations that are fundamental to programming.

Here's a brief rundown of the steps involved in the solution:

Iterate through each number in the nums array.
For each number, check if it is even. This can be done by looking at the least significant bit of the number. If the last bit is a 0, the number is even, and if it is a 1, the number is odd. In terms of bitwise operations, this check is equivalent to x & 1, which will be 0 for even numbers and 1 for odd numbers.
Count the total number of even numbers. Since we want to inverse the result of x & 1 to count even numbers, we use x & 1 ^ 1. The ^ 1 serves as a bitwise NOT operation for the least significant bit. This count can be achieved with the expression sum(x & 1 ^ 1 for x in nums) which adds up 1 for every even number and 0 for every odd number.
Check if the count of even numbers is at least 2. This corresponds to having at least two numbers with a trailing zero in their binary form.
Return true if there are two or more even numbers, and false otherwise.

The pythonic way showcased in the sum expression handles the iteration and counting elegantly in a single line. The use of bitwise AND (&) and XOR (^) operations provides an efficient way to check and count even numbers without resorting to conditional statements, while the neatness of list comprehension allows the entire operation to be composed concisely.

Therefore, the crux of our solution lies in the expression sum(x & 1 ^ 1 for x in nums) >= 2 which sums up a transformed list where even numbers contribute a count of 1 and odd numbers contribute a count of 0, and the comparison checks if the sum is greater than or equal to 2. If so, it implies the presence of two or more even numbers, which enables us to satisfy the condition set by the problem.

In conclusion, the solution is simple yet effective, leveraging basic bitwise operations to perform an even-number count in the array, which aligns with the necessary condition to solve the original problem.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's use a small example to illustrate the solution approach. Consider the array nums = [3, 5, 6, 8].

We will follow the steps outlined in the solution approach to determine if we can select two or more elements whose bitwise OR ends with at least one trailing zero.

Step-by-step Process:

We start by iterating through the array nums. Our array elements are 3, 5, 6, and 8.
Now, we inspect each number to see if it is even. Remember, even numbers in binary end with a 0, and odd numbers end with a 1.
- For 3 (binary 11), 3 & 1 yields 1, indicating it is odd.
- For 5 (binary 101), 5 & 1 yields 1, indicating it is odd.
- For 6 (binary 110), 6 & 1 yields 0, indicating it is even.
- For 8 (binary 1000), 8 & 1 yields 0, indicating it is even.
We count the number of even numbers by adding up 1s for each even number we encounter and 0s for each odd number. In our example, we have two even numbers (6 and 8), so our count is 2.
We check if our even count is at least 2. In our case, it is exactly 2, which satisfies the condition.
Since we found at least two even numbers, we return true. This indicates that it's possible to select elements from the array (specifically, 6 and 8 in our case) such that their bitwise OR will have at least one trailing zero. The binary OR of 6 (110) and 8 (1000) is 1110, which indeed has a trailing zero.

Thus, following the steps, we can see that our example input array [3, 5, 6, 8] allows us to select two numbers whose bitwise OR operation ends with a trailing zero. The approach yields a true result, confirming the solution.

Solution Implementation

1from typing import List  # Importing List type from typing module for type hinting
2
3class Solution:
4    def hasTrailingZeros(self, nums: List[int]) -> bool:
5        # Initialize a counter for the number of elements with trailing zeros
6        trailing_zero_count = 0
7      
8        # Iterate over each number in the list
9        for number in nums:
10            # Check if the last bit is 0 (which means the number is even)
11            if (number & 1) == 0:
12                # Increment the counter for numbers with trailing zero
13                trailing_zero_count += 1
14              
15            # If we already have at least two numbers with trailing zeros, return True
16            if trailing_zero_count >= 2:
17                return True
18      
19        # If the function hasn't returned yet, it means we have less than 2 numbers with trailing zeros
20        return False
21
22# This code assumes that having trailing zeros refers to numbers being even
23# (or in binary form, the least significant bit is 0).
24# The function returns True if there are 2 or more even numbers in the input list.
25

1class Solution {
2    // Method to determine if there are at least two trailing zeros in the binary representation of the numbers in the array
3    public boolean hasTrailingZeros(int[] nums) {
4        int countTrailingZeros = 0; // Initialize counter for trailing zeros
5      
6        // Iterate through each number in the array
7        for (int number : nums) {
8            // Add 1 to the counter if the least significant bit is 0 (even number), achieved by bitwise AND and XOR operations
9            countTrailingZeros += (number & 1 ^ 1);
10        }
11      
12        // Check if there are at least two numbers with trailing zeros (even numbers)
13        return countTrailingZeros >= 2;
14    }
15}
16

1class Solution {
2public:
3    // Function to determine if there exists two or more trailing zeros in the binary representation of any number in the array.
4    bool hasTrailingZeros(vector<int>& nums) {
5        // Initialize a counter for trailing zeros.
6        int countTrailingZeros = 0;
7      
8        // Iterate over each number in the array.
9        for (int number : nums) {
10            // Increment the counter if the least significant bit is not set (number is even).
11            countTrailingZeros += ((number & 1) ^ 1);
12        }
13      
14        // If there are two or more numbers with trailing zeros, return true.
15        return countTrailingZeros >= 2;
16    }
17};
18

1/**
2 * Check if the input array of numbers has at least two trailing zeros when
3 * represented in binary form.
4 * 
5 * @param {number[]} numbers - The array of numbers to check.
6 * @return {boolean} - Returns true if there are at least two trailing zeros, otherwise false.
7 */
8function hasTrailingZeros(numbers: number[]): boolean {
9    // Initialize a counter for the number of zeros
10    let zeroCount = 0;
11
12    // Loop through each number in the input array
13    for (const number of numbers) {
14        // For each number, we perform a bitwise AND with 1 (check if the number is even),
15        // and then XOR with 1 to flip the result. The count is incremented for even
16        // numbers (which have a trailing zero in binary).
17        zeroCount += (number & 1) ^ 1;
18    }
19
20    // If the count of trailing zeros is at least two, return true
21    return zeroCount >= 2;
22}
23

Time and Space Complexity

Time Complexity

The time complexity of the given code is O(n), where n is the length of the nums array. This complexity arises because the function iterates exactly once over all elements in the array to calculate the sum of (x & 1 ^ 1) for each x in nums. No other loops or nested iterations are present, so the entire operation scales linearly with the size of the input.

Space Complexity

The space complexity of the given code is O(1) which signifies constant space. This is because the space required does not increase with the size of the input array. The only extra space used is for the accumulator in the sum function, which does not depend on n, and basic variables needed to iterate through the array and compute the bitwise operations.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

Which of the following array represent a max heap?

20 12 16 1 2 3 4

20 30 10 5 6 7 18

30 20 11 2 3 4 12

50 30 40 10 20 30 40

I don’t know