Skip to content

3022. Minimize OR of Remaining Elements Using Operations 👍

  • Time: $O(30n) = O(n)$
  • Space: $O(1)$
 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
33
34
35
class Solution {
 public:
  int minOrAfterOperations(vector<int>& nums, int k) {
    constexpr int kMaxBit = 30;
    int ans = 0;
    int prefixMask = 0;  // Grows like: 10000 -> 11000 -> ... -> 11111.

    for (int i = kMaxBit; i >= 0; --i) {
      // Add the i-th bit to `prefixMask` and attempt to "turn off" the
      // currently added bit within k operations. If it's impossible, then we
      // add the i-th bit to the answer.
      prefixMask |= 1 << i;
      if (getMergeOps(nums, prefixMask, ans) > k)
        ans |= 1 << i;
    }

    return ans;
  }

 private:
  // Returns the number of merge operations to turn `prefixMask` to the target
  // by ANDing `nums`.
  int getMergeOps(const vector<int>& nums, int prefixMask, int target) {
    int mergeOps = 0;
    int ands = prefixMask;
    for (const int num : nums) {
      ands &= num;
      if ((ands | target) == target)
        ands = prefixMask;
      else
        ++mergeOps;  // Keep merging the next num.
    }
    return mergeOps;
  }
};

 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
33
class Solution {
  public int minOrAfterOperations(int[] nums, int k) {
    final int MAX_BIT = 30;
    int ans = 0;
    int prefixMask = 0; // Grows like: 10000 -> 11000 -> ... -> 11111.

    for (int i = MAX_BIT; i >= 0; --i) {
      // Add the i-th bit to `prefixMask` and attempt to "turn off" the
      // currently added bit within k operations. If it's impossible, then we
      // add the i-th bit to the answer.
      prefixMask |= 1 << i;
      if (getMergeOps(nums, prefixMask, ans) > k)
        ans |= 1 << i;
    }

    return ans;
  }

  // Returns the number of merge operations to turn `prefixMask` to the target
  // by ANDing `nums`.
  private int getMergeOps(int[] nums, int prefixMask, int target) {
    int mergeOps = 0;
    int ands = prefixMask;
    for (final int num : nums) {
      ands &= num;
      if ((ands | target) == target)
        ands = prefixMask;
      else
        ++mergeOps; // Keep merging the next num.
    }
    return mergeOps;
  }
}

 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
class Solution:
  def minOrAfterOperations(self, nums: list[int], k: int) -> int:
    MAX_BIT = 30
    ans = 0
    prefixMask = 0  # Grows like: 10000 -> 11000 -> ... -> 11111

    for i in range(MAX_BIT, -1, -1):
      # Add the i-th bit to `prefixMask` and attempt to "turn off" the
      # currently added bit within k operations. If it's impossible, then we
      # add the i-th bit to the answer.
      prefixMask |= 1 << i
      if self._getMergeOps(nums, prefixMask, ans) > k:
        ans |= 1 << i

    return ans

  def _getMergeOps(self, nums: list[int], prefixMask: int, target: int) -> int:
    """
    Returns the number of merge operations to turn `prefixMask` to the target
    by ANDing `nums`.
    """
    mergeOps = 0
    ands = prefixMask
    for num in nums:
      ands &= num
      if (ands | target) == target:
        ands = prefixMask
      else:
        mergeOps += 1  # Keep merging the next num
    return mergeOps