Smallest Number With All Set Bits solution and explanation
Google
9 more videos on this problem
Smallest Number With All Set Bits - Leetcode 3370 - PythonNeetCodeIO · 9:20 · 6K views
Smallest Number With All Set Bits | 3 Approaches | Something to learn | Leetcode 3370 | MIKcodestorywithMIK · 19:27 · 4K views
Daily Leetcode #2038: Oct 29, 2025 - 3370. Smallest Number With All Set BitsProgramming Live with Larry · 9:10 · 315 views
Smallest Number With All Set Bits | LeetCode 3370 | Bit ManipulationSanyam IIT Guwahati · 7:28 · 305 views
3370. Smallest Number With All Set Bits | Leetcode Daily - PythonLeetcode Daily · 7:51 · 221 views
3370. Smallest Number With All Set Bits (Leetcode Easy)Programming Live with Larry · 2:37 · 167 views
Smallest Number With All Set Bits | LeetCode 3370 - Pythonimpoldev · 5:35 · 156 views
LeetCode 3370 | Smallest Number With All Set Bits | Java Solution Explained Step-by-Step 💡Kalladi Sreevathsa · 5:59 · 120 views
Leetcode 3370 | Smallest Number With All Set Bits | Optimized Solution + CodeAlgo Optimizers · 4:47 · 102 views
LeetCode Daily 3370 | Smallest Number With All Set Bits | Easy | Solution WalkthroughDaily Dose Of LeetCode · 8:09 · 101 views
The problem
You are given a positive number n.
Return the smallest number x greater than or equal to n, such that the binary representation of x contains only set bits
Example 1:
Input: n = 5
Output: 7
Explanation:
The binary representation of 7 is "111".
Example 2:
Input: n = 10
Output: 15
Explanation:
The binary representation of 15 is "1111".
Example 3:
Input: n = 3
Output: 3
Explanation:
The binary representation of 3 is "11".
Constraints:
1 <= n <= 1000
Approach overview
Problem Overview: You are given an integer n. The task is to return the smallest number greater than or equal to n whose binary representation consists entirely of set bits (all 1s). Numbers like 1 (1), 3 (11), 7 (111), and 15 (1111) satisfy this property.
Approach 1: Iterative Incremental Approach (Time: O(ans - n), Space: O(1))
Start from n and keep incrementing the value until you find a number whose binary representation contains only set bits. A useful bit trick identifies such numbers: a value with all bits set satisfies x & (x + 1) == 0. This works because numbers like 111...111 become a power of two when incremented, which clears all lower bits. Iterate until the condition holds, then return that number. This approach is straightforward and easy to reason about, though in the worst case you may check several numbers before reaching the next valid one.
Approach 2: Bit Manipulation - Direct Calculation (Time: O(1), Space: O(1))
All numbers with every bit set follow the pattern 2^k - 1. The goal is to find the smallest such value that is greater than or equal to n. Observe that 2^k - 1 ≥ n when k ≥ ceil(log2(n + 1)). Compute k from the bit length of n, then return (1 << k) - 1. This avoids iteration entirely and directly constructs the correct number using bit shifts. The approach relies on patterns in binary representation and is a classic use of bit manipulation combined with simple math reasoning.
Recommended for interviews: The direct bit manipulation approach is what most interviewers expect. It demonstrates recognition of the 2^k - 1 pattern and comfort with binary operations. The iterative approach still helps show understanding of the property x & (x + 1) == 0, which is a common trick in bit manipulation problems.
Approach 1: Iterative Incremental Approach
This approach involves incrementing the number n until we find a number whose binary representation consists only of set bits (1s). The key observation here is that numbers like 3, 7, 15, etc., have all their bits set.
def smallest_set_bits(n):
x = n
while (x & (x + 1)) != 0:
x += 1
return x
print(smallest_set_bits(5))public class SmallestSetBits {
public static int smallestSetBits(int n) {
int x = n;
while ((x & (x + 1)) != 0) {
x++;
}
return x;
}
public static void main(String[] args) {
int n = 5;
System.out.println(smallestSetBits(n));
}
}#include <iostream>
using namespace std;
int smallestSetBits(int n) {
int x = n;
while ((x & (x + 1)) != 0) {
x++;
}
return x;
}
int main() {
int n = 5;
cout << smallestSetBits(n) << endl;
return 0;
}function smallestSetBits(n) {
let x = n;
while ((x & (x + 1)) !== 0) {
x++;
}
return x;
}
console.log(smallestSetBits(5));#include <stdio.h>
int smallestSetBits(int n) {
int x = n;
while ((x & (x + 1)) != 0) {
x++;
}
return x;
}
int main() {
int n = 5;
printf("%d\n", smallestSetBits(n));
return 0;
}using System;
class Program {
public static int SmallestSetBits(int n) {
int x = n;
while ((x & (x + 1)) != 0) {
x++;
}
return x;
}
static void Main(string[] args) {
Console.WriteLine(SmallestSetBits(5));
}
}The Python function iteratively checks if all bits in a number are set and returns the first such number greater than or equal to n.
Time Complexity: O(n)
Space Complexity: O(1)
Approach 2: Bit Manipulation - Direct Calculation
Instead of incrementing, this approach calculates the number directly using bit manipulation. The idea is to find the bit-length of n and return a number of all ones of that bit-length.
import math
def smallest_set_bits(n):
length = int(math.log2(n)) + 1
return (1 << length) - 1
print(smallest_set_bits(5))public class SmallestSetBits {
public static int smallestSetBits(int n) {
int length = (int)(Math.log(n) / Math.log(2)) + 1;
return (1 << length) - 1;
}
public static void main(String[] args) {
int n = 5;
System.out.println(smallestSetBits(n));
}
}#include <iostream>
#include <cmath>
using namespace std;
int smallestSetBits(int n) {
int length = (int)log2(n) + 1;
return (1 << length) - 1;
}
int main() {
int n = 5;
cout << smallestSetBits(n) << endl;
return 0;
}function smallestSetBits(n) {
const length = Math.floor(Math.log2(n)) + 1;
return (1 << length) - 1;
}
console.log(smallestSetBits(5));#include <stdio.h>
#include <math.h>
int smallestSetBits(int n) {
int length = (int)log2f(n) + 1;
return (1 << length) - 1;
}
int main() {
int n = 5;
printf("%d\n", smallestSetBits(n));
return 0;
}using System;
class Program {
public static int SmallestSetBits(int n) {
int length = (int)Math.Log(n, 2) + 1;
return (1 << length) - 1;
}
static void Main(string[] args) {
Console.WriteLine(SmallestSetBits(5));
}
}Python's math.log2 helps determine how many bits are required. Then, use bitwise operations to calculate the result.
Time Complexity: O(1)
Space Complexity: O(1)
Approach 3: Bit Manipulation
We start with x = 1 and continuously left shift x until x - 1 geq n. At this point, x - 1 is the answer we are looking for.
The time complexity is O(log n), and the space complexity is O(1).
function smallestNumber(n: number): number {
let x = 1;
while (x - 1 < n) {
x <<= 1;
}
return x - 1;
}func smallestNumber(n int) int {
x := 1
for x-1 < n {
x <<= 1
}
return x - 1
}impl Solution {
pub fn smallest_number(n: i32) -> i32 {
let mut x = 1;
while x - 1 < n {
x <<= 1;
}
x - 1
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Iterative Incremental Approach | Time Complexity: O(n) |
| Bit Manipulation - Direct Calculation | Time Complexity: O(1) |
| Bit Manipulation | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Iterative Incremental Approach | O(ans - n) | O(1) | Good for understanding the bit property x & (x + 1) == 0 and for quick brute-force style reasoning. |
| Bit Manipulation - Direct Calculation | O(1) | O(1) | Best for interviews and production code. Uses the 2^k - 1 pattern to compute the answer instantly. |
Frequently asked questions
Is Smallest Number With All Set Bits easy or hard?
Smallest Number With All Set Bits is classified as an Easy problem. The key insight is recognizing that valid answers follow the binary pattern 2^k - 1, which makes the optimal solution a short O(1) bit manipulation calculation.
Smallest Number With All Set Bits Python/Java solution
In Python or Java, compute k based on the bit length of n and return (1 << k) - 1. Python provides n.bit_length() for this calculation, while Java can use Integer.SIZE - Integer.numberOfLeadingZeros(n) to determine the required shift.
How to solve Smallest Number With All Set Bits in O(1)?
Use the property that numbers with all set bits equal 2^k - 1. Find the smallest k such that 2^k - 1 is greater than or equal to n, which can be derived from the bit length of n or using ceil(log2(n + 1)). Then return (1 << k) - 1.
What is the best approach for Smallest Number With All Set Bits?
The most efficient approach uses bit manipulation and the observation that numbers with all bits set follow the pattern 2^k - 1. Compute k = ceil(log2(n + 1)) and return (1 << k) - 1. This runs in O(1) time and O(1) space because it directly constructs the result without iteration.
Is Smallest Number With All Set Bits asked at Google/Amazon/Meta?
This problem reflects common interview patterns around bit manipulation and binary number properties. Variations involving powers of two, bit masks, or numbers of the form 2^k - 1 appear in interviews at companies like Amazon, Google, and Meta.
What data structure is used in Smallest Number With All Set Bits?
No complex data structures are required. The solution relies on mathematical reasoning and bit manipulation operations such as bit shifts and bitwise AND checks.
What is the time complexity of Smallest Number With All Set Bits?
The optimal bit manipulation solution runs in O(1) time and O(1) space because it calculates the answer using a simple formula. A brute-force incremental approach may take O(ans - n) time in the worst case since it checks numbers sequentially until it finds one with all bits set.