Welcome to Subscribe On Youtube

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

  • 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;
    }
}


  • 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;
    }
};


  • 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


  • 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
}


  • 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;
}

All Problems

All Solutions