","934","static/chunks/app/cs/problems/%5Bslug%5D/page-935d3f20891d8cfc.js"],"default"] 17:I[4821,["874","static/chunks/874-64ff3adb125f84b1.js","269","static/chunks/269-5f9235f83b944543.js","222","static/chunks/222-e37d1f81e0d6d2ef.js","934","static/chunks/app/cs/problems/%5Bslug%5D/page-935d3f20891d8cfc.js"],"default"] 18:I[2647,["874","static/chunks/874-64ff3adb125f84b1.js","269","static/chunks/269-5f9235f83b944543.js","222","static/chunks/222-e37d1f81e0d6d2ef.js","934","static/chunks/app/cs/problems/%5Bslug%5D/page-935d3f20891d8cfc.js"],"default"] 1a:I[7912,["874","static/chunks/874-64ff3adb125f84b1.js","269","static/chunks/269-5f9235f83b944543.js","222","static/chunks/222-e37d1f81e0d6d2ef.js","934","static/chunks/app/cs/problems/%5Bslug%5D/page-935d3f20891d8cfc.js"],"default"] 19:Td3c,

Problem

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.

Examples

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

Solution

Method 1 – Bitwise Greedy

Intuition

To make the bitwise AND of [x, n] equal to 0, we need to ensure that every bit position is zeroed out in the AND. The smallest power of two greater than n will have all lower bits set in the range [x, n] for some x. The answer is the smallest x such that [x, n] covers a full power of two, i.e., x = n + 1 - 2^k where 2^k is the smallest power of two greater than n.

Approach

Find the smallest power of two greater than n (let's call it p).
The answer is x = p - n - 1.
Return x.

Code

[{"language":"C++","code":"class Solution {\npublic:\n    int maximumX(int n) {\n        int p = 1;\n        while (p <= n) p <<= 1;\n        return p - n - 1;\n    }\n};","lang":"cpp"},{"language":"Go","code":"func maximumX(n int) int {\n    p := 1\n    for p <= n {\n        p <<= 1\n    }\n    return p - n - 1\n}","lang":"go"},{"language":"Java","code":"class Solution {\n    public int maximumX(int n) {\n        int p = 1;\n        while (p <= n) p <<= 1;\n        return p - n - 1;\n    }\n}","lang":"java"},{"language":"Kotlin","code":"class Solution {\n    fun maximumX(n: Int): Int {\n        var p = 1\n        while (p <= n) p = p shl 1\n        return p - n - 1\n    }\n}","lang":"kotlin"},{"language":"Python","code":"class Solution:\n    def maximumX(self, n: int) -> int:\n        p = 1\n        while p <= n:\n            p <<= 1\n        return p - n - 1","lang":"python"},{"language":"Rust","code":"impl Solution {\n    pub fn maximum_x(n: i32) -> i32 {\n        let mut p = 1;\n        while p <= n {\n            p <<= 1;\n        }\n        p - n - 1\n    }\n}","lang":"rust"},{"language":"TypeScript","code":"class Solution {\n    maximumX(n: number): number {\n        let p = 1;\n        while (p <= n) p <<= 1;\n        return p - n - 1;\n    }\n}","lang":"typescript"}]

Complexity

⏰ Time complexity: O(log n) — We find the next power of two.

Related Tags