# Q4. Find Nth Smallest Integer with K One Bits

**練習日期：** 2026-01-25
**類型：** Weekly Contest 486

## 📘 題目敘述

給你兩個正整數 `n` 和 `k`。

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

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

### 條件限制

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

## 🧠 解題思路（最後TLE）

我的想法是：
我先用一個 `bin`（bool 陣列）表示「目前這個數的二進位哪些位元是 1」，並且從最小的開始（也就是最低位連續放 `k` 個 1：`111...000`）。

接著我要做的事情就是重複 `n-1` 次：
**把目前的 bitmask 變成「下一個更大的、但 1 的數量仍然是 k」的 bitmask**。

這其實是在做「固定 1 的個數的下一個組合（next combination）」。

### 所有變數

* `n, k`：題目輸入，要找第 `n` 小、且有 `k` 個 1 的正整數
* `bin`：`vector<bool>`，`bin[t] = true` 代表第 `t` 個 bit 是 1（我用 `t=0` 當最低位）
* `pos`：目前最高的 1 出現到哪個 bit（用來最後把 `bin` 轉回數字時的最高位）
* `ans`：最後要回傳的整數
* `orot / nrot`（這題沒有）
* `count`：掃描過程中，累計「目前遇到的 1 的數量」（用來把低位重新塞回去）
* `i, j, l`：迴圈索引用

## 🪜 主要流程步驟

### 1) 初始化成「最小的那個」

* 最小的數一定是：最低位開始連續放 `k` 個 1
例如 `k=3` → `0b111`

所以我先做：

* `bin[0..k-1] = true`
* 其餘都是 `false`

---

### 2) 重複做 `n-1` 次：產生下一個 bitmask（核心）

我在每一次迭代裡，從低位往高位掃描，找「可以往左移動的一顆 1」：

#### 我在找的關鍵形狀

* 找到某個位置 `j` 滿足：

* `bin[j] == 1`
* `bin[j+1] == 0`

這代表這顆 1 可以「往更高位推一格」，讓整體數值變大，但仍保留 k 個 1。

#### 做法分兩步

**(A) 把這顆 1 往左推**

* `bin[j] = 0`
* `bin[j+1] = 1`
* 同時更新 `pos = max(pos, j+1)`（因為最高位可能變大了）

**(B) 把 `j` 左邊的低位重新整理成「最小」**

* 我會用 `count` 記錄我一路走來遇到多少個 1（包含要搬的那顆之前累積的）
* 當找到可搬動位置後，我就把 `0..j-1` 的 bit 重新排成：

* 從最低位開始塞回 `count` 顆 1
* 其餘補 0
這樣可以確保：
在「固定高位變大的前提下」，低位保持最小，才能得到「下一個最小的合法數」。

---

### 3) 把 `bin` 轉回整數

最後我從 `pos`（最高位）一路往 `0` 組回去：

* 每一位做：`ans = ans * 2 + (bin[l] ? 1 : 0)`

## 💻 程式碼實作

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/contest/weekly-contest-486/problems/find-nth-smallest-integer-with-k-one-bits/description/