Skip to content

3495. Minimum Operations to Make Array Elements Zero 👍

  • Time: $O(q)$
  • 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
class Solution {
 public:
  long long minOperations(vector<vector<int>>& queries) {
    long ans = 0;
    for (const vector<int>& query : queries) {
      const int l = query[0];
      const int r = query[1];
      ans += (getOperations(r) - getOperations(l - 1) + 1) / 2;
    }
    return ans;
  }

 private:
  // Returns the number of operations required for [1, n].
  long getOperations(int n) {
    long res = 0;
    int ops = 0;
    for (int powerOfFour = 1; powerOfFour <= n; powerOfFour *= 4) {
      const int l = powerOfFour;
      const int r = min(n, powerOfFour * 4 - 1);
      res += static_cast<long>(r - l + 1) * ++ops;
    }
    return res;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
  public long minOperations(int[][] queries) {
    long ans = 0;
    for (int[] query : queries) {
      final int l = query[0];
      final int r = query[1];
      ans += (getOperations(r) - getOperations(l - 1) + 1) / 2;
    }
    return ans;
  }

  // Returns the number of operations required for [1, n].
  private long getOperations(int n) {
    long res = 0;
    int ops = 0;
    for (int powerOfFour = 1; powerOfFour <= n; powerOfFour *= 4) {
      final int l = powerOfFour;
      final int r = Math.min(n, powerOfFour * 4 - 1);
      res += (long) (r - l + 1) * ++ops;
    }
    return res;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution:
  def minOperations(self, queries: list[list[int]]) -> int:
    return sum((self._getOperations(r) - self._getOperations(l - 1) + 1) // 2
               for l, r in queries)

  def _getOperations(self, n: int) -> int:
    """Returns the number of operations required for [1, n]."""
    res = 0
    ops = 0
    powerOfFour = 1
    while powerOfFour <= n:
      l = powerOfFour
      r = min(n, powerOfFour * 4 - 1)
      ops += 1
      res += (r - l + 1) * ops
      powerOfFour *= 4
    return res