Smallest Number With All Set Bits · Interview Problem

Back to problems

Leetcode

Medium

Bit Manipulation

Math

Smallest Number With All Set Bits

Find the smallest integer whose binary representation contains exactly the same number of set bits as the given number.

Acceptance 0%

Start Practice

Problem Statement

Given a positive integer $n$ , return the smallest positive integer $x$ such that $x$ has the same number of set bits (1s) in its binary representation as $n$ .

In other words, if $n$ contains $k$ set bits, your task is to find the minimum possible value of an integer with exactly $k$ set bits.

Input Format

A single positive integer $n$ .

Output Format

Return the smallest positive integer that has the same number of set bits as $n$ .

Constraints

$1 \le n$
The answer fits in the usual integer range for the platform.

Examples

Sample cases returned by the problem API.

Example 1

Input

n = 5

Output

Explanation

5 in binary is 101, which has 2 set bits. The smallest positive integer with 2 set bits is 11 in binary, which is 3.

Example 2

Input

n = 12

Output

Explanation

12 in binary is 1100, which has 2 set bits. The smallest number with 2 set bits is 3 (11 in binary).

Premium problem context

Unlock deeper context for this problem

Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.

Guided hints

Editorial and discussion links

Concept map and variants

Track your progress