3495. Minimum Operations to Make Array Elements Zero

Leetcode link

题目简介

这是一道 hard，题目给我们一个二维数组，数组中包含多个 [left, right] 形式的数组，代表从 left 到 right 的正整数

题目要求我们每次操作都从 l 到 r 中任意选择两个数字，并将其处以 4 后向下取整，直到数组中所有数字都变为 0

最后返回所有数组需要的操作次数

解题思路

这道题有两种解法，但是都服务于一个相同的思路，下面我们先聊聊解题思路

首先我们先来分析一下，任意一个数字被 4 整除之后向下取整需要几步：

• 对于 1, 2, 3 来说，只需要一步，因为他们小于 $4^1$
• 对于 4, 5, ..., 15 来说，需要两步，因为他们小于 $4^2$
• 对于 16, 17, ..., 63 来说，需要三步，因为他们小于 $4^3$
• 以此类推

知道了这个规律之后，我们不难想到可以针对 l 到 r 的正整数序列进行分堆，然后针对每一堆的数量乘以他们需要的步骤之后相加，就可以求得任意一个 [left, right] 组合中每一个数字变为 0 需要的步骤了，最后再将其除以 2 之后向上取整，就能得到题目所求的操作次数了

举个例子：有一个数组是 [3, 17]

我们可以将其分为三组：

• 3 自己一组，因为它只需要一次除法
• 4~15 一组，因为他们需要两次除法
• 16, 17 一组，因为需要三次除法

我们可以得到需要 31 (1*1 + (15-4+1) * 2 + 2 * 3) 次除法才能够将所有数字变为 0，那么题目需要的操作次数就是 Ceil(31/2) = 16

了解了这个思路之后，接下来有两种解决方案：

• 用数字来寻找相同组
• 遍历所有组，并找到各组内的数字

用数字寻找组

用数字寻找范围的精髓在于，通过题目给出的数字，来判断他们分别属于哪些范围，然后再进行求和计算

为了算法的通用性，我们可以设计一个能够计算 [1, n] 这个范围的算法，这样一来如果题目要求是 [left, right]，我们可以用 [1, right] 需要的除法计算减去 [1, left-1]需要的除法次数，然后再除以 2 向上取整就可以计算出题目所需的操作数量了

Javascript

/**
 * @param {number[][]} queries
 * @return {number}
 */
var minOperations = function (queries) {
    let result = 0n
    queries.forEach(([l, r]) => {
        const leftOpCount = totalNeedOfOpsToNum(l - 1)
        const rightOpCount = totalNeedOfOpsToNum(r)
        result += (rightOpCount - leftOpCount + 1n) / 2n
    })
    return Number(result)
};

// 将数字分组，最后加总所需除法次数
const totalNeedOfOpsToNum = num => {
    let res = 0n;
    let needOfOps = 1;
    let base = 1;

    while (base <= num) {
        const end = Math.min(base * 2 - 1, num);
        res += BigInt(Math.floor((needOfOps + 1) / 2)) * BigInt(end - base + 1);
        needOfOps++;
        base *= 2;
    }
    return res;
}

用组寻找数字

换一个角度来思考题目，如果我们可以知道总共有多少组，我们是不是就可以通过遍历所有的组来寻找各自组别有的数字了呢？

我们可以看到题目对 left 跟 right 的 $1 \le l \lt r \le 10^9$

题目要求的除数是 4，所以我们可以知道这个组最多不超过 $log_{4}10^9 \lt 15$

于是我们就可以针对每一组 [l, r]，进行一次循环，从而找出所需要进行除法的次数

Javascript

/**
 * @param {number[][]} queries
 * @return {number}
 */
var minOperations = function (queries) {
    let res = 0;

    queries.forEach(([left, right]) => {
        let needOfOps = 0

        for (let i = 1; i <= 15; i++) {
            // the upper bound must be 4^i - 1
            const upperBound = (1 << (2 * i)) - 1

            if (upperBound < left) continue

            const upper = Math.min(upperBound, right)
            needOfOps += (upper - left + 1) * i

            if (upper === right) break;

            left = upperBound + 1
        }

        res += Math.ceil(needOfOps / 2)
    })

    return res
};