3821. Find Nth Smallest Integer with K One Bits

📘 題目敘述

給你兩個正整數 n 和 k。

請回傳「二進位表示中恰好有 k 個 1」的正整數裡，第 n 小的那一個。

題目保證答案嚴格小於 2^50。

條件限制

• 1 <= n <= 250
• 1 <= k <= 50
• 答案嚴格小於 2^50

🧠 解題思路（最後TLE）

用 bitmask 模擬「固定 1 的個數的下一個組合」，從最小的 111...000 開始，重複找下一個合法 bitmask。

所有變數

• n, k：要找第 n 小且有 k 個 1 的正整數
• bin：vector<bool>，代表哪些位元是 1
• pos：目前最高位 1 的位置
• ans：最後要回傳的答案
• count：掃描時累計的 1 數量
• i, j, l：迴圈索引

🪜 主要流程步驟

1) 初始化成最小的 bitmask

• 最低位連續放 k 個 1

2) 重複 n - 1 次：產生下一個 bitmask

• 找第一個滿足 bin[j] == 1 且 bin[j + 1] == 0 的位置
• 把這顆 1 往左推，並把低位重新排成最小

3) 把 bitmask 轉回整數

• 從最高位 pos 開始組回答案

💻 程式碼實作

class Solution {
public:
    long long nthSmallest(long long n, int k) {
        long long int ans = 0;
        int pos = k - 1;
        vector<bool> bin(51, false);
        for (int i = 0; i < k; i++) {
            bin[i] = true;
        }
        for (long long int i = 1; i < n; i++) {
            int count = 0;
            for (int j = 0; j < 50; j++) {
                if (bin[j] && !bin[j + 1]) {
                    bin[j + 1] = true;
                    bin[j] = false;
                    pos = (pos > j + 1) ? pos : (j + 1);
                    for (int k = 0; k < j; k++) {
                        if (count > 0) {
                            bin[k] = true;
                            count--;
                        } else {
                            bin[k] = false;
                        }
                    }
                    break;
                } else if (bin[j]) {
                    count++;
                }
            }
        }
        for (int l = pos; l >= 0; l--) {
            ans = ans * 2 + (bin[l] ? 1 : 0);
        }
        return ans;
    }
};

🔗 題目連結

https://leetcode.com/problems/find-nth-smallest-integer-with-k-one-bits/