Maximum Number That Makes Result of Bitwise AND Zero

Maximum Number That Makes Result of Bitwise AND Zero - 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.

The bitwise AND operation compares each bit position of two numbers and returns 1 only when both bits are 1, otherwise returns 0.

When we AND all numbers in a range, we need to find the largest starting point where this result becomes 0.

Input & Output

Example 1 — Basic Case

$ Input: n = 5

› Output: 0

💡 Note: For x=0, the range [0,5] includes 0&1&2&3&4&5 = 0. Since the range includes 0 and 0 AND anything equals 0, x=0 gives the maximum valid answer.

Example 2 — Single Number

$ Input: n = 1

› Output: 0

💡 Note: For x=0, the range [0,1] computes 0&1 = 0. This gives AND result 0, so x=0 is the maximum answer.

Example 3 — Edge Case Zero

$ Input: n = 0

› Output: 0

💡 Note: For x=0, the range [0,0] contains only 0, and AND of 0 is 0. So x=0 is the answer.

Constraints

0 ≤ n ≤ 10⁹

Visualization

Tap to expand

Understanding the Visualization

Input

Given integer n = 5

Process

Find max x where AND of [x,n] = 0

Output

Return x = 0

Key Takeaway

🎯 Key Insight: Since 0 AND any number equals 0, starting from x=0 always produces AND result 0, making it the maximum valid answer

Asked in

G Google 15 M Microsoft 12 a Amazon 8

The key insight is that any range starting from 0 will always have AND result 0, since 0 AND anything equals 0. The optimal approach uses this mathematical property to return 0 in constant time. Time: O(1), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force	O(n²)	O(1)	Try all possible starting points x and check if AND of range [x,n] equals 0
Bit Manipulation Analysis	O(log n)	O(1)	Analyze bit patterns to find where consecutive ranges will produce 0
Mathematical Pattern Recognition	O(1)	O(1)	Use the mathematical insight that for any n, x=0 always works as the maximum

Brute Force — Algorithm Steps

Start from x = n and go down to 0
For each x, calculate AND of all numbers from x to n
Return the first x where AND equals 0

Visualization

Tap to expand

Step-by-Step Walkthrough

Start from x=n

Begin with maximum possible x

Calculate AND

Compute AND of range [x,n]

Check Result

If AND=0, return x, else try x-1

Code -

solution.c — C

#include <stdio.h>

int solution(int n) {
    for (int x = n; x >= 0; x--) {
        int result = x;
        for (int i = x + 1; i <= n; i++) {
            result &= i;
            if (result == 0) break;
        }
        if (result == 0) return x;
    }
    return 0;
}

int main() {
    int n;
    scanf("%d", &n);
    int result = solution(n);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

Outer loop runs n times, inner loop averages n/2 operations

⚠ Quadratic Growth

Space Complexity

O(1)

Only using constant extra variables

✓ Linear Space

12.3K Views

Medium Frequency

~15 min Avg. Time

485 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler