Smallest Number With All Set Bits

Easy
729.

Smallest Number With All Set Bits

Smallest Number With All Set Bits is an easy coding problem on math and bit manipulation, asked in Amazon, TCS and Capgemini interviews.

Return the smallest number x that is at least n and whose binary representation is all ones — that is, x is 1, 3, 7, 15, 31, and so on.

Example 1

Input
n = 5
Output
7
Explanation
7 is 111 in binary and is the smallest all-ones value at or above 5.

Example 2

Input
n = 10
Output
15

Example 3

Input
n = 3
Output
3
Explanation
3 is already all ones.

Constraints

  • 1 <= n <= 1000
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} n
 * @return {number}
 */
var smallestNumber = function(n) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Smallest Number With All Set Bits — Problem & Solution

Smallest Number With All Set Bits solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.

Smallest Number With All Set Bits is an easy coding problem on math and bit manipulation, asked in Amazon, TCS and Capgemini interviews.

  • Difficulty: Easy
  • Topics: Math, Bit Manipulation
  • Asked at: Amazon, TCS, Capgemini
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Return the smallest number x that is at least n and whose binary representation is all ones — that is, x is 1, 3, 7, 15, 31, and so on.

Example 1

Input: n = 5
Output: 7
Explanation: 7 is 111 in binary and is the smallest all-ones value at or above 5.

Example 2

Input: n = 10
Output: 15

Example 3

Input: n = 3
Output: 3
Explanation: 3 is already all ones.

Constraints

  • 1 <= n <= 1000

Hints for Smallest Number With All Set Bits

  1. Hint 1

    The all-ones numbers are exactly 2^k - 1.

  2. Hint 2

    Start at 1 and repeatedly append a one bit — v = 2v + 1 — until you reach or pass n.

  3. Hint 3

    No search is needed; there are only about ten such values in range.

How to solve Smallest Number With All Set Bits

All-ones numbers form the sequence 1, 3, 7, 15, …, each obtained from the previous by appending a one bit. Walk the sequence until it reaches n.

Approach

  1. Start v at 1.
  2. While v < n, replace v with 2v + 1.
  3. Return v.

Why it works

2v + 1 shifts the binary form left and sets the new low bit, so the sequence enumerates 2^k - 1 in increasing order. The first term at or above n is therefore the smallest such value.

Complexity

  • Time — O(log n)
  • Space — O(1)

Pitfalls

  • Starting at 0 never escapes — 2 * 0 + 1 = 1 works, but v = 0 with v *= 2 would not.
  • Rounding n up to a power of two gives 8 for n = 5, which is not all ones.

Reference solution

Python

def smallestNumber(n: int) -> int:
    v = 1
    while v < n:
        v = v * 2 + 1
    return v

Java

public static int smallestNumber(int n) {
    int v = 1;
    while (v < n) v = v * 2 + 1;
    return v;
}

C++

int smallestNumber(int n) {
    int v = 1;
    while (v < n) v = v * 2 + 1;
    return v;
}

JavaScript

var smallestNumber = function(n) {
    var v = 1;
    while (v < n) v = v * 2 + 1;
    return v;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 337 math problems · the whole catalogue

Learn the technique: Bit Manipulation