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

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.