3125. Maximum Number That Makes Result of Bitwise AND Zero 🔒

Problem Description

Given an integer n, your task is to return the maximum integer x such that x <= n, and the bitwise AND of all the numbers within the range [x, n] results in 0.

Intuition

To solve this problem, we need to identify the highest bit that is set to 1 in the binary representation of n. The goal is to find the maximum integer x such that:

x is less than or equal to n.
The bitwise AND operation for the range [x, n] results in 0.

For the range [x, n] to AND to 0, x must be such that when it is incremented by 1, the result combined using AND with x is 0. This scenario occurs when x is made up of all bits set to 1 up to the position just below the highest bit set in n. Essentially, if the binary length of n is k bits, x is formed by setting all k-1 bits to 1 (i.e., x = 2^{k-1} - 1). This results in x being the largest value less than n that satisfies the bitwise AND condition.

Learn more about Greedy and Sorting patterns.

Solution Approach

The solution leverages bit manipulation to find the desired value of x. Here’s a step-by-step breakdown of the approach:

Identify the Highest Bit: First, determine the position of the highest set bit in the binary representation of n. This can be effectively achieved using the bit_length() method on the integer n, which returns the number of bits required to represent n in binary.
Calculate x: Using the position identified, compute x as 2^{(n.bit_length() - 1)} - 1. This formula works because 2^{k} - 1 gives a binary number with all bits set to 1 up to the k-1 position. Here, k is the number of bits in the binary representation of n.
Return the Result: This computed value of x ensures that it is the maximum number less than or equal to n where the bitwise AND with numbers in the range [x, n] equals 0.

The implementation of this logic in code is concise:

class Solution:
    def maxNumber(self, n: int) -> int:
        return (1 << (n.bit_length() - 1)) - 1

In this implementation, 1 << (n.bit_length() - 1) effectively computes 2^{(n.bit_length() - 1)}, shifting the 1 left to the desired bit position. Subtracting 1 then results in a number with all bits set below this position, giving the required x.

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 walk through an example to better understand the solution approach. Suppose we have n = 10. Our goal is to find the maximum integer x such that x <= 10 and the bitwise AND of all numbers in the range [x, 10] is 0.

Identify the Binary Representation: First, let's determine the binary representation of 10, which is 1010.
Find the Highest Set Bit: The highest set bit in 10 is in the 2(^3) position (counting from zero). The binary length of 10 is, therefore, 4.
Calculate x: We use the bit length to compute x as (2^{(4 - 1)} - 1 = 2^3 - 1 = 8 - 1 = 7). In binary, x equals 0111.
Verification: Now, check if this value of x satisfies the condition. Consider the range [7, 10]:
- 7 in binary: 0111
- 8 in binary: 1000
- 9 in binary: 1001
- 10 in binary: 1010
The bitwise AND of all these numbers is 0000, which is indeed 0. Therefore, x = 7 is the maximum integer meeting our conditions.

Thus, applying the bit manipulation technique effectively gives us the correct result: x = 7.

Solution Implementation

1class Solution:
2    def maxNumber(self, n: int) -> int:
3        # Calculate the bit length of the number n
4        bit_length = n.bit_length()
5
6        # Calculate the maximum number with all 1s in binary representation
7        # This is equivalent to (2^(bit_length-1)) - 1
8        max_number_with_ones = (1 << (bit_length - 1)) - 1
9
10        # Return the computed maximum number
11        return max_number_with_ones
12

1class Solution {
2    public long maxNumber(long n) {
3        // Find the position of the highest set bit in 'n'
4        int highestSetBitPosition = 63 - Long.numberOfLeadingZeros(n);
5
6        // Calculate the maximum number with all bits set below the highest set bit position.
7        // This is achieved by left-shifting 1 to create a number with all bits set '0', then subtracting 1.
8        return (1L << highestSetBitPosition) - 1;
9    }
10}
11

1#include <iostream>
2#include <climits>
3
4class Solution {
5public:
6    // Method to find the maximum number with the same number of bits set as the given number
7    long long maxNumber(long long n) {
8        // Calculate the number of leading zero bits in the binary representation of n
9        int leadingZeroBits = __builtin_clzll(n);
10      
11        // Shift left by (63 - leadingZeroBits), which gives us the highest bit position of n
12        // Subtract 1 to fill all lower bits with 1
13        return (1LL << (63 - leadingZeroBits)) - 1;
14    }
15};
16

1// Function to find the maximum number with the same number of bits set as the given number
2function maxNumber(n: bigint): bigint {
3    // Calculate the number of leading zero bits in the binary representation of n
4    let leadingZeroBits: number = countLeadingZeros(n);
5  
6    // Shift left by (63 - leadingZeroBits), which gives us the highest bit position of n
7    // Subtract 1 to fill all lower bits with 1
8    return (1n << BigInt(63 - leadingZeroBits)) - 1n;
9}
10
11// Helper function to count leading zeros in a 64-bit integer
12function countLeadingZeros(n: bigint): number {
13    let count: number = 0;
14    const totalBits: number = 64;
15  
16    // Iterate over the bits from left to right
17    for (let i = totalBits - 1; i >= 0; i--) {
18        if ((n & (1n << BigInt(i))) === 0n) {
19            count++;
20        } else {
21            break;
22        }
23    }
24    return count;
25}
26

Time and Space Complexity

The time complexity of the code is O(log n) because the bit_length() function determines the number of bits required to represent the integer n in binary, which is proportional to the logarithm of n. Therefore, computing bit_length() takes O(log n) time.

The space complexity of the code is O(1) because it uses a constant amount of additional space, independent of the input size n.

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

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

Question 1 out of 10

How does quick sort divide the problem into subproblems?

Divide the array into two equal halves by index

Divide the array into two based on whether an element is smaller than an arbitrary value

Divide the array into a stray element and the rest of the array

Quick sort does not use divide and conquer

I don’t know