Watch 7 video solutions for Find Nth Smallest Integer With K One Bits, a hard level problem involving Math, Bit Manipulation, Combinatorics. This walkthrough by Sanyam IIT Guwahati has 1,494 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 = 1125 = 10126 = 11029 = 10012Example 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 = 122 = 1024 = 1002
Constraints:
1 <= n <= 2501 <= k <= 50250.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.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Enumeration | O(ans * log ans) | O(1) | Good for understanding the problem or when n is extremely small |
| Combinatorics + Greedy Bit Construction | O(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 |