Skip to content

3858. Minimum Bitwise OR From Grid

Description

You are given a 2D integer array grid of size m x n.

You must select exactly one integer from each row of the grid.

Return an integer denoting the minimum possible bitwise OR of the selected integers from each row.

 

Example 1:

Input: grid = [[1,5],[2,4]]

Output: 3

Explanation:

  • Choose 1 from the first row and 2 from the second row.
  • The bitwise OR of 1 | 2 = 3​​​​​​​, which is the minimum possible.

Example 2:

Input: grid = [[3,5],[6,4]]

Output: 5

Explanation:

  • Choose 5 from the first row and 4 from the second row.
  • The bitwise OR of 5 | 4 = 5​​​​​​​, which is the minimum possible.

Example 3:

Input: grid = [[7,9,8]]

Output: 7

Explanation:

  • Choosing 7 gives the minimum bitwise OR.

 

Constraints:

  • 1 <= m == grid.length <= 105
  • 1 <= n == grid[i].length <= 105
  • m * n <= 105
  • 1 <= grid[i][j] <= 105​​​​​​​

Solutions

Solution 1

Thinking

Pick one number per row to minimize the bitwise OR. At most \(10^5\) cells, so selections cannot be enumerated.

We want high bits of the OR to stay \(0\). Try bits from high to low: given higher bits already fixed, ask whether every row still has a value compatible with those bits (lower bits free).

For the trial mask \(\textit{ans} \mid (2^i-1)\), if each row has an \(x\) covered by the mask, the current bit may stay \(0\); otherwise it must be set.

High-bit-first filling yields the minimum OR.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution:
    def minimumOR(self, grid: List[List[int]]) -> int:
        mx = max(map(max, grid))
        m = mx.bit_length()
        ans = 0
        for i in range(m - 1, -1, -1):
            mask = ans | ((1 << i) - 1)
            for row in grid:
                found = False
                for x in row:
                    if (x | mask) == mask:
                        found = True
                        break
                if not found:
                    ans |= 1 << i
                    break
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
    public int minimumOR(int[][] grid) {
        int mx = 0;
        for (int[] row : grid) {
            for (int x : row) {
                mx = Math.max(mx, x);
            }
        }

        int m = 32 - Integer.numberOfLeadingZeros(mx);
        int ans = 0;

        for (int i = m - 1; i >= 0; i--) {
            int mask = ans | ((1 << i) - 1);
            for (int[] row : grid) {
                boolean found = false;
                for (int x : row) {
                    if ((x | mask) == mask) {
                        found = true;
                        break;
                    }
                }
                if (!found) {
                    ans |= 1 << i;
                    break;
                }
            }
        }

        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
public:
    int minimumOR(vector<vector<int>>& grid) {
        int mx = 0;
        for (auto& row : grid) {
            mx = max(mx, ranges::max(row));
        }

        int m = 32 - __builtin_clz(mx);
        int ans = 0;

        for (int i = m - 1; i >= 0; i--) {
            int mask = ans | ((1 << i) - 1);
            for (auto& row : grid) {
                bool found = false;
                for (int x : row) {
                    if ((x | mask) == mask) {
                        found = true;
                        break;
                    }
                }
                if (!found) {
                    ans |= 1 << i;
                    break;
                }
            }
        }

        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
func minimumOR(grid [][]int) int {
    mx := 0
    for _, row := range grid {
        mx = max(mx, slices.Max(row))
    }

    m := bits.Len(uint(mx))
    ans := 0

    for i := m - 1; i >= 0; i-- {
        mask := ans | ((1 << i) - 1)
        for _, row := range grid {
            found := false
            for _, x := range row {
                if (x | mask) == mask {
                    found = true
                    break
                }
            }
            if !found {
                ans |= 1 << i
                break
            }
        }
    }

    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
function minimumOR(grid: number[][]): number {
    let mx = 0;
    for (const row of grid) {
        mx = Math.max(mx, Math.max(...row));
    }

    const m = mx === 0 ? 0 : 32 - Math.clz32(mx);
    let ans = 0;

    for (let i = m - 1; i >= 0; i--) {
        const mask = ans | ((1 << i) - 1);
        for (const row of grid) {
            let found = false;
            for (const x of row) {
                if ((x | mask) === mask) {
                    found = true;
                    break;
                }
            }
            if (!found) {
                ans |= 1 << i;
                break;
            }
        }
    }

    return ans;
}

Comments