1class Solution {
2    // Upper bound for the number of bits we consider (covers values up to 2^49).
3    private static final int MAX_BITS = 50;
4
5    // Precomputed Pascal's triangle: binomial[i][j] = C(i, j),
6    // i.e. the number of ways to choose j items out of i.
7    private static final long[][] binomial = new long[MAX_BITS][MAX_BITS + 1];
8
9    // Static initializer: build the binomial coefficient table once at class load time.
10    static {
11        for (int i = 0; i < MAX_BITS; i++) {
12            // There is exactly one way to choose 0 items.
13            binomial[i][0] = 1;
14            // Standard Pascal's triangle recurrence: C(i, j) = C(i-1, j-1) + C(i-1, j).
15            for (int j = 1; j <= i; j++) {
16                binomial[i][j] = binomial[i - 1][j - 1] + binomial[i - 1][j];
17            }
18        }
19    }
20
21    /**
22     * Returns the n-th smallest non-negative integer whose binary representation
23     * contains exactly k set bits (1-indexed by n).
24     *
25     * Strategy: decide each bit from the highest position down to the lowest.
26     * For bit position i, the number of valid integers that have a 0 at bit i
27     * (and the remaining k set bits placed among the lower i positions) is C(i, k).
28     * If n is within that range, bit i stays 0; otherwise we must set bit i,
29     * subtract the skipped count, and reduce the remaining set-bit budget k.
30     *
31     * @param n the 1-indexed rank of the desired value
32     * @param k the exact number of set bits required
33     * @return the n-th smallest integer with exactly k set bits
34     */
35    public long nthSmallest(long n, int k) {
36        long ans = 0;
37
38        // Iterate from the highest considered bit down to bit 0.
39        for (int i = 49; i >= 0; i--) {
40            // C(i, k) counts how many valid numbers keep bit i as 0.
41            if (n > binomial[i][k]) {
42                // Skip all those candidates that have bit i = 0.
43                n -= binomial[i][k];
44                // Set bit i in the answer.
45                ans |= 1L << i;
46                // One fewer set bit remains to be placed.
47                k--;
48                // Once all required set bits are placed, the result is complete.
49                if (k == 0) {
50                    break;
51                }
52            }
53        }
54
55        return ans;
56    }
57}
58

1// Maximum number of bits we consider (covers values up to ~2^49).
2constexpr int kMaxBits = 50;
3
4// comb[i][j] = C(i, j), the number of ways to choose j items from i.
5long long comb[kMaxBits][kMaxBits + 1];
6
7// Precompute Pascal's triangle once at program startup.
8// The lambda is invoked immediately, and its return value initializes a dummy variable.
9const auto kInit = [] {
10    for (int i = 0; i < kMaxBits; ++i) {
11        comb[i][0] = 1;  // C(i, 0) = 1
12        for (int j = 1; j <= i; ++j) {
13            // Pascal's identity: C(i, j) = C(i-1, j-1) + C(i-1, j).
14            comb[i][j] = comb[i - 1][j - 1] + comb[i - 1][j];
15        }
16    }
17    return 0;
18}();
19
20class Solution {
21public:
22    // Returns the n-th smallest positive integer (1-indexed) whose binary
23    // representation contains exactly k set bits.
24    long long nthSmallest(long long n, int k) {
25        long long answer = 0;
26
27        // Decide each bit from the most significant (49) down to the least (0).
28        for (int i = 49; i >= 0; --i) {
29            // comb[i][k] counts how many numbers can be formed using the lower
30            // i bit positions with k bits still to place (i.e. leaving bit i unset).
31            // If n is larger, those candidates are skipped, so bit i must be set.
32            if (n > comb[i][k]) {
33                n -= comb[i][k];     // Skip the candidates that leave bit i unset.
34                answer |= 1LL << i;  // Set bit i in the answer.
35
36                // One set bit has been placed; if no more are needed, we are done.
37                if (--k == 0) {
38                    break;
39                }
40            }
41        }
42
43        return answer;
44    }
45};
46

1// Maximum number of bits / table dimension
2const MAX_BITS = 50;
3
4// binomial[i][j] stores C(i, j) = "i choose j", using BigInt for large values
5const binomial: bigint[][] = Array.from({ length: MAX_BITS }, () =>
6    Array(MAX_BITS + 1).fill(0n)
7);
8
9// Precompute Pascal's triangle:
10// C(i, 0) = 1, and C(i, j) = C(i-1, j-1) + C(i-1, j)
11for (let i = 0; i < MAX_BITS; i++) {
12    binomial[i][0] = 1n;
13    for (let j = 1; j <= i; j++) {
14        binomial[i][j] = binomial[i - 1][j - 1] + binomial[i - 1][j];
15    }
16}
17
18/**
19 * Find the n-th smallest non-negative integer whose binary representation
20 * contains exactly k set bits (ones).
21 *
22 * Strategy: Decide each bit from the highest position down to the lowest.
23 * For a given bit position i, the number of valid integers that keep this
24 * bit as 0 (i.e. all remaining k ones are placed among the lower i bits)
25 * is C(i, k). If n falls within that count, leave the bit unset; otherwise
26 * set this bit, subtract that count, and reduce the number of ones still
27 * needed (k) by one.
28 *
29 * @param n The 1-based rank of the desired number.
30 * @param k The required number of set bits.
31 * @returns The n-th smallest integer with exactly k set bits.
32 */
33function nthSmallest(n: number, k: number): number {
34    // remaining rank we still need to skip past
35    let remainingRank = BigInt(n);
36    // the result accumulated bit by bit
37    let result = 0n;
38
39    // Iterate bit positions from the highest down to the lowest
40    for (let bit = 49; bit >= 0; bit--) {
41        // Count of numbers with this bit unset and k ones in the lower bits
42        const count = binomial[bit][k];
43
44        // If the rank exceeds this count, this bit must be set
45        if (remainingRank > count) {
46            remainingRank -= count;
47            result |= 1n << BigInt(bit);
48
49            // One fewer set bit is needed; stop once all ones are placed
50            if (--k === 0) {
51                break;
52            }
53        }
54    }
55
56    return Number(result);
57}
58