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

Maximum Number That Makes Result of Bitwise AND Zero

Number: 3433

Difficulty: Medium

Paid? Yes

Companies: Salesforce

Problem Description

Given an integer n, return the maximum integer x such that x <= n, and the bitwise AND of all the numbers in the range [x, n] equals 0.

Key Insights

  • The bitwise AND of a range becomes 0 if every bit position has at least one number in the range with a 0.
  • For any given n, identify the position of the most significant bit (MSB) using floor(log2(n)).
  • By choosing x = (1 << msb) - 1, we ensure that the range [x, n] covers all combinations for the lower bits, forcing the overall AND to be 0.
  • This approach works for both cases where n is a power of two and when n is of the form (2^k - 1).

Space and Time Complexity

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

Solution

The solution relies on determining the most significant bit (MSB) of n. The key observation is that starting from x = (1 << msb) - 1 guarantees that in the range [x, n], every bit position is unset (i.e., becomes 0) at least in one number. This is because the numbers in that range will have all variations of bits below the MSB. The approach uses bit manipulation and logarithmic functions to compute the final answer in constant time.

Code Solutions

def max_and_zero(n):
    # Compute the position of the most significant bit (floor(log2(n)))
    msb = n.bit_length() - 1
    # Return (1 << msb) - 1 as the maximum x for which the AND becomes 0
    return (1 << msb) - 1

# Example usage:
n = 17
print(max_and_zero(n))  # Output: 15
← Back to All Questions