3495. Minimum Operations to Make Array Elements Zero
思路:
從題目可以知道1個數字x要變成0需要花的次數
是取決於floor(log4(x)) + 1
假設位於 4^n ~ 4^(n+1) -1間的數字有i個
那需要花費的次數就為(n+1) * i
接著照上面的方法計算出每個query所需要的總次數 step
因為每次可以選兩個數次出來/4
所以要將step / 2, 如果是奇數還要再 + 1
最後算完所有query就可以得到答案了
golang code :
func minOperations(queries [][]int) int64 {
ans := 0
interval := make([][2]int, 0, 31)
for i := 0; i < 31; i++ {
interval = append(interval, [2]int{1 << (2 * i), 1<<(2*(i+1)) - 1})
}
for _, query := range queries {
n := int(log4(float64(query[1])))
l, r := -1, -1
s := 0
for l != query[0] {
l, r = max(interval[n][0], query[0]), min(interval[n][1], query[1])
num := (r - l + 1)
s += num * (n + 1)
n