Is Maximum Number That Makes Result of Bitwise AND Zero easy or hard?

The problem is rated Medium because the brute force idea is simple but inefficient. Recognizing that the AND result stays non-zero only when all numbers share a common set bit requires bit manipulation insight.

Maximum Number That Makes Result of Bitwise AND Zero Python/Java solution

The implementation iterates through each number and checks all bit positions using bit shifts. Maintain an array of size 32 (for 32-bit integers) to count set bits. The final answer is the maximum value in this frequency array. This logic works the same in Python, Java, C++, and Go.

How to solve Maximum Number That Makes Result of Bitwise AND Zero in O(n)?

Treat the number of bits in an integer as constant (typically 32). Iterate through the array once and count occurrences of each set bit. The largest frequency among those bits represents the maximum subset whose AND keeps that bit, effectively giving an O(n) practical solution.

What is the best approach for Maximum Number That Makes Result of Bitwise AND Zero?

The optimal approach uses bit manipulation with bit frequency counting. Count how many numbers contain each bit position and take the maximum count. If multiple numbers share a specific set bit, their AND keeps that bit, ensuring the result stays non-zero. This runs in O(n log A) time where A is the maximum value.

Is Maximum Number That Makes Result of Bitwise AND Zero asked at Google/Amazon/Meta?

Bit manipulation and greedy counting problems appear frequently in interviews at companies like Google, Amazon, and Meta. Variants involving maximizing subsets based on shared bits or AND/OR constraints are common in coding interviews.

What data structure is used in Maximum Number That Makes Result of Bitwise AND Zero?

The solution mainly uses simple counters or an array to track how many numbers contain each bit position. No complex data structures are required beyond basic arrays and bitwise operations.

What is the time complexity of Maximum Number That Makes Result of Bitwise AND Zero?

The optimal bit counting solution runs in O(n log A) time because each number is checked across its bit positions. Space complexity is O(log A) for maintaining counts of each bit position.

Description Hints 3 Solution Video 6:06

3125. Maximum Number That Makes Result of Bitwise AND Zero

Medium70.0% acceptance1 companyPremium elsewhere, free here

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 <= 10¹⁵

Asked at 1 company

Salesforce

Topics

Hints open one at a time

Hint 1

Examine the set bits of n.

Hint 2

When performing bitwise AND operations sequentially down from n, the last set bit to turn to 0 identifies the highest set bit.

Hint 3

If the index of the highest set bit is x, the answer is 2^x - 1.

6:06

Still stuck?Read the written solution, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
  def solve(self):
      pass


Starter codePython 3Spaces: 4

Examples

Case 1Case 2Case 3

Input

Your code is saved on this device.Solution