README_EN.md

comments	difficulty	edit_url	tags
true	Medium	https://github.com/doocs/leetcode/edit/main/solution/3100-3199/3125.Maximum%20Number%20That%20Makes%20Result%20of%20Bitwise%20AND%20Zero/README_EN.md	Greedy String Sorting

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)$.

Python3

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

Java

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

C++

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

Go

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