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

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] is 0.

 

Example 1:

Input: n = 7

Output: 3

Explanation:

The bitwise AND of [6, 7] is 6.
The bitwise AND of [5, 6, 7] is 4.
The bitwise AND of [4, 5, 6, 7] is 4.
The bitwise AND of [3, 4, 5, 6, 7] is 0.

Example 2:

Input: n = 9

Output: 7

Explanation:

The bitwise AND of [7, 8, 9] is 0.

Example 3:

Input: n = 17

Output: 15

Explanation:

The bitwise AND of [15, 16, 17] is 0.

 

Constraints:

• 1 <= n <= 1015

Solutions

Solution 1: Bit Manipulation

We can find the highest bit of \(1\) in the binary representation of \(n\). The maximum \(x\) must be less than \(n\) and this bit is \(0\), and all other lower bits are \(1\), i.e., \(x = 2^{\textit{number of the highest bit}} - 1\). This is because \(x \textit{ and } (x + 1) = 0\) must hold.

The time complexity is \(O(\log n)\), and the space complexity is \(O(1)\).

Python3JavaC++Go

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

class Solution {
    public long maxNumber(long n) {
        return (1L << (63 - Long.numberOfLeadingZeros(n))) - 1;
    }
}

class Solution {
public:
    long long maxNumber(long long n) {
        return (1LL << (63 - __builtin_clzll(n))) - 1;
    }
};

func maxNumber(n int64) int64 {
    return int64(1<<(bits.Len64(uint64(n))-1)) - 1
}

Comments