3314. Construct the Minimum Bitwise Array I

📘 題目敘述

你會拿到一個陣列 nums，其中包含 n 個質數（prime integers）。

你需要建立一個長度同為 n 的陣列 ans，並且對每個 i 滿足：

• ans[i] | (ans[i] + 1) == nums[i]
• 在所有能滿足條件的 ans[i] 中，選擇最小的那個
• 如果不存在任何 ans[i] 能滿足條件，則令 ans[i] = -1

請回傳陣列 ans。

條件限制

• 1 <= nums.length <= 100
• 2 <= nums[i] <= 1000
• nums[i] 是質數（prime）

🧠 解題思路

我這份程式的核心想法很直覺：對於每個 nums[i]，我就從 j = 0 一路試到 j = nums[i] - 1，找出第一個滿足 (j | (j + 1)) == nums[i] 的 j。

因為我是從小到大試，所以一旦找到就一定是最小的答案。如果整段都找不到，就保持 -1。

所有變數

• n：nums 的長度
• ans：答案陣列，一開始先全部填 -1（代表預設找不到）
• i：目前在處理第幾個 nums[i]
• j：我用來暴力嘗試的候選答案（想找最小的 ans[i]）

🪜 主要流程步驟

1. 先把答案陣列初始化成全 -1

• ans 一開始全部是 -1
• 代表如果後面暴力試完都沒有成功，就自然保留 -1

2. 外層：逐一處理每個 nums[i]

• 我會對每個 nums[i] 各自找一個最小的 j

3. 內層：從小到大暴力測試 j

• 我讓 j 從 0 一路試到 nums[i] - 1
• 每次都檢查一次條件：(j | (j + 1)) == nums[i]

情況一：找到第一個符合的 j

• 立刻令 ans[i] = j
• break 跳出內層迴圈（因為已經是最小的 j 了）

情況二：整段都找不到

• ans[i] 會維持初始化的 -1
• 代表這個 nums[i] 沒有任何解

最後回傳 ans 就是答案了。

💻 程式碼實作

class Solution {
public:
    vector<int> minBitwiseArray(vector<int>& nums) {
        int n = nums.size();
        vector<int> ans(n, -1);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < nums[i]; j++) {
                if ((j | (j + 1)) == nums[i]) {
                    ans[i] = j;
                    break;
                }
            }
        }
        return ans;
    }
};

🔗 題目連結

https://leetcode.com/problems/construct-the-minimum-bitwise-array-i/