Skip to main content
Talentd

Find Nth Smallest Integer With K One Bits - Solution & Explanation

HardMathBit ManipulationCombinatorics9 min readAsked at: Google
Practice this problem

Problem Statement

You are given two positive integers n and k.

Return an integer denoting the nth smallest positive integer that has exactly k ones in its binary representation. It is guaranteed that the answer is strictly less than 250.

 

Example 1:

Input: n = 4, k = 2

Output: 9

Explanation:

The 4 smallest positive integers that have exactly k = 2 ones in their binary representations are:

  • 3 = 112
  • 5 = 1012
  • 6 = 1102
  • 9 = 10012

Example 2:

Input: n = 3, k = 1

Output: 4

Explanation:

The 3 smallest positive integers that have exactly k = 1 one in their binary representations are:

  • 1 = 12
  • 2 = 102
  • 4 = 1002

 

Constraints:

  • 1 <= n <= 250
  • 1 <= k <= 50
  • The answer is strictly less than 250.

Approach Overview

Problem Overview: Given integers n and k, return the n-th smallest positive integer whose binary representation contains exactly k set bits (1s). Numbers are ordered by their numeric value, so the task becomes generating the n-th value among all integers that contain exactly k ones.

Approach 1: Brute Force Enumeration (Exponential / Practical O(ans * log ans))

Start from 1 and iterate upward. For each number, count the number of set bits using a bit trick such as n & (n - 1) or a built‑in popcount. Whenever the count equals k, increment a counter. Stop once the counter reaches n. The method is simple and demonstrates understanding of bit manipulation, but it becomes extremely slow because the answer may be very large. Time complexity is roughly O(ans * log ans) due to repeated bit counting, with O(1) extra space.

Approach 2: Combinatorics + Greedy Bit Construction (Optimal, O(log ans))

Instead of enumerating integers, construct the number bit by bit. For each potential bit position from high to low, calculate how many integers can be formed if that position is set to 0 while still placing the remaining k ones in the lower bits. This count equals the binomial coefficient C(remaining_bits, remaining_ones). If the count is smaller than n, skip those numbers, subtract the count from n, and place a 1 at that position. Otherwise keep the bit 0 and continue. This greedy decision process directly jumps over large blocks of numbers using combinatorics and avoids enumeration. Time complexity is O(log ans) for iterating through bit positions and computing combinations, with O(1) space if binomial coefficients are computed on the fly.

Approach 3: Combinatorial Number System (Combinadics) (O(k log ans))

Another view treats the binary representation as choosing k bit positions among many possible positions. The n-th integer corresponds to the n-th combination in lexicographic order of these positions. Using combinadic ranking/unranking, you determine each set bit position by comparing n with binomial counts such as C(i, r). This technique also relies heavily on math and combinatorics. Time complexity is O(k log ans) because each chosen bit requires evaluating combination counts, with O(1) space.

Recommended for interviews: The combinatorics + greedy approach. It shows you understand how to count combinations of bit placements and skip entire numeric ranges instead of brute forcing. Mentioning the brute force approach first demonstrates baseline reasoning, but the optimal solution proves you can apply combinatorial counting and bit construction efficiently.

Solution

We need to find the n-th smallest positive integer that contains exactly k ones in its binary representation. We can determine each bit from the most significant to the least significant, deciding whether it is 0 or 1.

Suppose we are currently processing the i-th bit (from 49 down to 0). If we set this bit to 0, then the remaining k ones need to be chosen from the lower i bits, and the number of possible combinations is C(i, k). If n is greater than C(i, k), it implies that the i-th bit of the n-th number must be 1. In this case, we set this bit to 1, subtract C(i, k) from n, and decrement k by 1 (since we have already used one 1). Otherwise, we set this bit to 0.

We repeat the above process until all bits are processed or k becomes 0.

The time complexity is O(log^2 M), and the space complexity is O(log^2 M), where M is the upper bound of the answer, 2^{50}.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force EnumerationO(ans * log ans)O(1)Good for understanding the problem or when n is extremely small
Combinatorics + Greedy Bit ConstructionO(log ans)O(1)Optimal approach for large n; skips entire ranges using binomial counts
Combinatorial Number System (Combinadics)O(k log ans)O(1)Useful when directly mapping the n-th combination of k bit positions

Video Solution

Nth Smallest Integer With K Set Bits | LeetCode 3821 | Weekly Contest 486 • Sanyam IIT Guwahati • 1,564 views views

Watch 5 more video solutions →

Frequently Asked Questions

Is Find Nth Smallest Integer With K One Bits easy or hard?
The problem is typically classified as Hard because it requires combining bit manipulation with combinatorial counting. Brute force solutions are straightforward but inefficient, while the optimal solution requires understanding how to count combinations and construct the result greedily.
Find Nth Smallest Integer With K One Bits Python/Java solution
Implement the greedy combinatorial approach. Iterate through bit positions from high to low, compute C(remaining_bits, remaining_ones), and decide whether to place a 0 or 1 at that position. The same logic works across Python, Java, C++, Go, and TypeScript with a helper function for binomial coefficients.
How to solve Find Nth Smallest Integer With K One Bits in O(log N)?
Build the number from the most significant bit downward. At each position, compute how many numbers exist if that bit remains 0 while distributing the remaining k ones among lower bits using C(remaining_bits, remaining_ones). If the count is less than n, subtract it and set the bit to 1. Otherwise keep it 0 and continue.
What is the best approach for Find Nth Smallest Integer With K One Bits?
The optimal approach uses combinatorics with greedy bit construction. For each bit position, compute how many numbers can be formed if the bit is 0 using binomial coefficients like C(n, k). If that count is smaller than the remaining index, subtract it and place a 1. This skips entire ranges of integers and runs in about O(log ans) time with O(1) space.
Is Find Nth Smallest Integer With K One Bits asked at Google/Amazon/Meta?
Variants of this problem appear in interviews at companies that emphasize combinatorics and bit manipulation, including Google, Amazon, and Meta. Interviewers use it to test understanding of binomial coefficients, greedy construction, and efficient bit-level reasoning rather than brute-force enumeration.
What data structure is used in Find Nth Smallest Integer With K One Bits?
The solution mainly relies on mathematical counting rather than complex data structures. It uses binary representation of integers, bit operations, and binomial coefficient calculations from combinatorics. Only constant extra variables are needed to track remaining bits and ones.
What is the time complexity of Find Nth Smallest Integer With K One Bits?
The optimal combinatorics + greedy solution runs in O(log ans) time because it processes each bit position once while computing combination counts. Space complexity is O(1). A naive brute force solution that checks every integer until the nth valid one appears can take roughly O(ans * log ans) time due to repeated popcount operations.

Ready to solve this problem?

Practice Find Nth Smallest Integer With K One Bits with our built-in code editor and test cases.

Practice on FleetCode
Previous

Add Two Numbers

Next

Reverse Integer