• Leetcode 3495. Minimum Operations to Make Array Elements Zero
  • 1. 解題思路
  • 2. 代碼實現

• 題目鏈接：3495. Minimum Operations to Make Array Elements Zero

1. 解題思路

這一題的話核心就是統計對任意自然數$n$，從$1$到$n$當中所有的數字對于$4$的階數之和，用數學公式表達就是：
$$f(n)=\sum _{i=1}^n?{\log }_4(i)?$$

當然，直接的計算這個問題還是比較復雜的，不過我們可以通過迭代的方式對其進行計算，顯然$1,2,3$三個數可以一次操作直接處理了，對于剩余的$4$到$n$，我們可以按照對其$4$的余數進行分組，然后進行一次除以$4$的操作，從而得到$4$組$1$到$?\frac{n}{4}?$的數，這樣，我們就將問題簡化到從求$1$到$n$變成了求$1$到$?\frac{n}{4}?$了。迭代我們即可得到我們最終的問題的解。

然后，有了上述函數$f(n)$之后，事實上我們就得到了任意范圍$[l,r]$只能的$4$的階數的和$s$，而要使之變為$0$，其所需要的操作次數事實上就是$?\frac{s}{2}?$。

綜上，我們將其翻譯為代碼語言即可。

2. 代碼實現

給出python代碼實現如下：

@lru_cache(None)
def count4(n):if n < 4:return nans = 3for r in range(4):k = (n-r) // 4ans += k + count4(k)return ansclass Solution:def minOperations(self, queries: List[List[int]]) -> int:ans = 0for l, r in queries:need = count4(r)-count4(l-1)ans += (need+1)//2return ans

提交代碼評測得到：耗時4619ms，占用內存556MB。