C++C py3 log4 prefix sum, bits解Leetcode難題3495 Minimum Operations to Mak...

C++C py3 log4 prefix sum/bits解Leetcode難題3495  Minimum Operations to Make Array Elements Zero

ceil(log4(x)) 可以透過 clz 計算；將 expSum 定義為部分和來計算。

[Py3 code請進]

ceil(log4(x)) can be computed by clz; define expSum as partial sum to compute.

[codes on Leetcode]https://leetcode.com/problems/minimum-operations-to-make-array-elements-zero/solutions/7159801/sum-of-exponent-1-of-base-4-beats-100/

[bit/ bitmask playlist]https://www.youtube.com/watch?v=Hw1fnQA8Nk8&list=PLYRlUBnWnd5K8FlzJ6tOswqQcsk7R1Duh

class Solution:
    def minOperations(self, queries: List[List[int]]) -> int:
        expSum4=[1]+[0]*17
        def expSum(x):
            if x==0: return 0
            log4=(x.bit_length()-1)>>1
            r=x-(1<<(log4<<1))
            return expSum4[log4]+r*(log4+1)
        for i in range(1,18):
            expSum4[i]=expSum4[i-1]+3*i*(1<<(2*(i-1)))+1
        op=0
        for l1, r in queries:
            op+=(expSum(r)-expSum(l1-1)+1)>>1

        return op