algoadvance

Leetcode 2980. Check if Bitwise OR Has Trailing Zeros

Problem Statement

Given a non-negative integer n, you need to determine whether the bitwise OR of this number and any one-bit number (i.e., a number that has exactly one 1-bit) has trailing zeros. Trailing zeros are zeros in the least significant positions of a binary number.

Example:

  1. Input: n = 8 (binary representation: 1000) Output: True Explanation: The bitwise OR of 8 with 1s at positions 0, 1, and 2 does not have trailing zeros, but with 1 at position 3, it still has trailing zeros. As there exists at least one one-bit number that when OR’ed with 8 still results in trailing zeros, the result is True.

Clarifying Questions

  1. What range can the input integer n fall within?
    • Typically, n will be a non-negative integer within the range of 32-bit or 64-bit integers.
  2. What will be considered as trailing zeros?
    • Trailing zeros refer to sequences of zeros that occur at the end of the binary representation of the number.

Strategy

  1. Understand trailing zeros and bitwise OR operation:
    • Trailing zeros in a number n can be observed by looking at the binary form from the least significant bit onwards.
    • The number of trailing zeros in n can be determined using n & (-n), which gives us the least significant 1-bit as a power of two. The number of trailing zeros corresponds to the position of this bit.
  2. Evaluate different cases:
    • If n has trailing zeros, then the bitwise OR with any number that has the 1-bit higher than or equal to the position of the least significant 1-bit of n will keep the trailing zeros intact.
  3. Procedure to determine trailing zeros:
    • Get the number of trailing zeros in n.
    • Loop through one-bit numbers with a 1 in positions greater than or equal to the position of the least significant 1-bit of n to see if trailing zeros are maintained.

Code

Here’s the implementation of the solution in C++:

#include <iostream>

bool hasTrailingZeros(int n) {
    if (n == 0) {
        return true; // OR with any 1-bit number will be non-zero, hence will have trailing zeros.
    }
    
    // Calculate the number of trailing zeros in n
    int trailingZerosCount = __builtin_ctz(n);
    
    // Generate a number with exactly one 1-bit in the position `trailingZerosCount`
    int positionBit = 1 << trailingZerosCount;
    
    // Check if OR operation with this number maintains trailing zeros
    int result = n | positionBit;
    return (__builtin_ctz(result) > trailingZerosCount);
}

int main() {
    int n = 8; // Example input
    bool result = hasTrailingZeros(n);
    std::cout << (result ? "True" : "False") << std::endl;
    
    return 0;
}

Time Complexity

The time complexity of this solution is O(1) because:

  1. Calculating the number of trailing zeros using __builtin_ctz is a constant time operation, which is hardware-assisted.
  2. The bitwise OR operation is also a constant time operation.
  3. The operations and condition checks are performed in constant time.

Thus, this approach has efficient time complexity suitable for a competitive programming environment.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI