Overflow in intermediate arithmetic
Wrong move: Temporary multiplications exceed integer bounds.
Usually fails on: Large inputs wrap around unexpectedly.
Fix: Use wider types, modular arithmetic, or rearranged operations.
Build confidence with an intuition-first walkthrough focused on math fundamentals.
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 <= 1000Problem summary: 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
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Math · Bit Manipulation
5
10
3
minimum-number-of-k-consecutive-bit-flips)minimum-bit-flips-to-convert-number)find-sum-of-array-product-of-magical-sequences)Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #3370: Smallest Number With All Set Bits
class Solution {
public int smallestNumber(int n) {
int x = 1;
while (x - 1 < n) {
x <<= 1;
}
return x - 1;
}
}
// Accepted solution for LeetCode #3370: Smallest Number With All Set Bits
func smallestNumber(n int) int {
x := 1
for x-1 < n {
x <<= 1
}
return x - 1
}
# Accepted solution for LeetCode #3370: Smallest Number With All Set Bits
class Solution:
def smallestNumber(self, n: int) -> int:
x = 1
while x - 1 < n:
x <<= 1
return x - 1
// Accepted solution for LeetCode #3370: Smallest Number With All Set Bits
impl Solution {
pub fn smallest_number(n: i32) -> i32 {
let mut x = 1;
while x - 1 < n {
x <<= 1;
}
x - 1
}
}
// Accepted solution for LeetCode #3370: Smallest Number With All Set Bits
function smallestNumber(n: number): number {
let x = 1;
while (x - 1 < n) {
x <<= 1;
}
return x - 1;
}
Use this to step through a reusable interview workflow for this problem.
Sort the array in O(n log n), then scan for the missing or unique element by comparing adjacent pairs. Sorting requires O(n) auxiliary space (or O(1) with in-place sort but O(n log n) time remains). The sort step dominates.
Bitwise operations (AND, OR, XOR, shifts) are O(1) per operation on fixed-width integers. A single pass through the input with bit operations gives O(n) time. The key insight: XOR of a number with itself is 0, which eliminates duplicates without extra space.
Review these before coding to avoid predictable interview regressions.
Wrong move: Temporary multiplications exceed integer bounds.
Usually fails on: Large inputs wrap around unexpectedly.
Fix: Use wider types, modular arithmetic, or rearranged operations.