Q3. Minimum Bitwise OR From Grid

📘 題目敘述

你會拿到一個大小為 m x n 的 2D 整數陣列 grid。你必須每一列剛好選出一個整數，回傳全部選值做 bitwise OR 後的最小可能值。

條件限制

• 1 <= m == grid.length <= 10^5
• 1 <= n == grid[i].length <= 10^5
• m * n <= 10^5
• 1 <= grid[i][j] <= 10^5

🧠 解題思路

我把「處理到第 i 列的所有可能 OR 值」存成集合。初始為 {0}，每加入一列就把上一輪集合中的每個值，和本列每個數做 OR，形成新集合。最後集合裡的最小值就是答案。

所有變數

• s：目前所有可能 OR 結果集合
• ns：下一列的新集合
• ans：最終最小 OR 值

🪜 主要流程步驟

1. 初始化

s = {0}。

2. 逐列做狀態轉移

枚舉 s 與當列所有數，將 x | y 放進 ns，再令 s = ns。

3. 取最小值

掃過最後的 s 取最小值。

⏱️ 複雜度

• 時間複雜度：概念上 O(m * n * U)
• 空間複雜度：O(U)

💻 程式碼實作

class Solution {
public:
    int minimumOR(vector<vector<int>>& grid) {
        unordered_set<int> s;
        s.insert(0);
        for (auto& a : grid) {
            unordered_set<int> ns;
            for (int x : s) {
                for (int y : a) {
                    ns.insert(x | y);
                }
            }
            s = ns;
        }
        int ans = INT_MAX;
        for (int z : s) {
            ans = min(ans, z);
        }
        return ans;
    }
};

🔗 題目連結

https://leetcode.com/contest/weekly-contest-491/problems/minimum-bitwise-or-from-grid/