diff options
author | Jack Sangdahl <[email protected]> | 2025-09-05 22:09:03 -0600 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2025-09-05 22:09:03 -0600 |
commit | 8eca342b99ab30a60285fc842f0229ab60ba2bcc (patch) | |
tree | f440631fa4ce02042a27db631f47fc2e5abec366 /min_ops_arr_elem_zero.py | |
parent | 4efcf3f8df8a89adbef6018a9d2b9c1a2fee7ddf (diff) | |
download | leetcode-8eca342b99ab30a60285fc842f0229ab60ba2bcc.tar.gz leetcode-8eca342b99ab30a60285fc842f0229ab60ba2bcc.zip |
3495. minimum operations to make array elements zero
Diffstat (limited to 'min_ops_arr_elem_zero.py')
-rw-r--r-- | min_ops_arr_elem_zero.py | 37 |
1 files changed, 37 insertions, 0 deletions
diff --git a/min_ops_arr_elem_zero.py b/min_ops_arr_elem_zero.py new file mode 100644 index 0000000..d164c77 --- /dev/null +++ b/min_ops_arr_elem_zero.py @@ -0,0 +1,37 @@ +# 3495. Minimum Operations to Make Array Elements Zero + +""" +you are given a 2d array 'queries' where 'queries[i]' is of the form '[l, +r]'. each 'queries[i]' defines an array of integers 'nums' consisting of +elements ranging from 'l' to 'r' both inclusive. in one operation you can +select two integers 'a' and 'b' from the array and replace them with 'floor(a +/ 4)' and 'floor(b / 4)'. your task is to determine the minimum number of +operations required to reduce all the elements of the array to zero for each +query. return the sum of the results for all queries. +""" + + +class Solution(object): + def count(self, a): + res, k, v = 0, 1, 1 + while a >= v * 4: + res += (v * 4 - v) * k + k += 1 + v *= 4 + return res + (a - v + 1) * k + + def minOperations(self, queries): + """ + :type queries: List[List[int]] + :rtype: int + """ + ans = 0 + for l, r in queries: + ans += (self.count(r) - self.count(l - 1)) // 2 + return ans + + +if __name__ == "__main__": + obj = Solution() + print(obj.minOperations(queries=[[1, 2], [2, 4]])) + print(obj.minOperations(queries=[[2, 6]])) |