Skip to content

3097. Shortest Subarray With OR at Least K II 👍

  • Time: $O(30n) = O(n)$
  • Space: $O(30) = 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
36
37
38
39
class Solution {
 public:
  // Same as 3095. Shortest Subarray With OR at Least K I
  int minimumSubarrayLength(vector<int>& nums, int k) {
    constexpr int kMax = 50;
    const int n = nums.size();
    int ans = n + 1;
    int ors = 0;
    vector<int> count(kMax + 1);

    for (int l = 0, r = 0; r < n; r++) {
      ors = orNum(ors, nums[r], count);
      while (ors >= k && l <= r) {
        ans = min(ans, r - l + 1);
        ors = undoOrNum(ors, nums[l], count);
        ++l;
      }
    }

    return (ans == n + 1) ? -1 : ans;
  }

 private:
  static constexpr int kMaxBit = 30;

  int orNum(int ors, int num, vector<int>& count) {
    for (int i = 0; i < kMaxBit; ++i)
      if (num >> i & 1 && ++count[i] == 1)
        ors += 1 << i;
    return ors;
  }

  int undoOrNum(int ors, int num, vector<int>& count) {
    for (int i = 0; i < kMaxBit; ++i)
      if (num >> i & 1 && --count[i] == 0)
        ors -= 1 << i;
    return ors;
  }
};

 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
36
37
class Solution {
  // Same as 3095. Shortest Subarray With OR at Least K I
  public int minimumSubarrayLength(int[] nums, int k) {
    final int kMax = 50;
    final int n = nums.length;
    int ans = n + 1;
    int ors = 0;
    int[] count = new int[kMax + 1];

    for (int l = 0, r = 0; r < n; ++r) {
      ors = orNum(ors, nums[r], count);
      while (ors >= k && l <= r) {
        ans = Math.min(ans, r - l + 1);
        ors = undoOrNum(ors, nums[l], count);
        ++l;
      }
    }

    return (ans == n + 1) ? -1 : ans;
  }

  private static final int kMaxBit = 30;

  private int orNum(int ors, int num, int[] count) {
    for (int i = 0; i < kMaxBit; ++i)
      if ((num >> i & 1) == 1 && ++count[i] == 1)
        ors += 1 << i;
    return ors;
  }

  private int undoOrNum(int ors, int num, int[] count) {
    for (int i = 0; i < kMaxBit; ++i)
      if ((num >> i & 1) == 1 && --count[i] == 0)
        ors -= 1 << i;
    return ors;
  }
}

 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:
  # Same as 3095. Shortest Subarray With OR at Least K I
  def minimumSubarrayLength(self, nums: list[int], k: int) -> int:
    ans = len(nums) + 1
    ors = 0
    count = collections.Counter()

    l = 0
    for r, num in enumerate(nums):
      ors = self._orNum(ors, num, count)
      while ors >= k and l <= r:
        ans = min(ans, r - l + 1)
        ors = self._undoOrNum(ors, nums[l], count)
        l += 1

    return -1 if ans == len(nums) + 1 else ans

  def _orNum(self, ors: int, num: int, count: dict[int, int]) -> int:
    for i in range(30):
      if num >> i & 1:
        count[i] += 1
        if count[i] == 1:
          ors += 1 << i
    return ors

  def _undoOrNum(self, ors: int, num: int, count: dict[int, int]) -> int:
    for i in range(30):
      if num >> i & 1:
        count[i] -= 1
        if count[i] == 0:
          ors -= 1 << i
    return ors