3954. 区间内的兼容数字之和 I

来源第 505 场周赛 Q1难度简单分数1210

题目描述

给你两个整数 n 和 k。

如果一个正整数 x 同时满足以下两个条件，则称其为兼容整数：

abs(n - x) <= k
(n & x) == 0

返回所有兼容整数 x 的总和。

注意：

这里，& 表示 按位与 运算符。
整数 i 和 j 之间的绝对差定义为 abs(i - j)。

示例 1：

输入： n = 2, k = 3

输出： 10

解释：

兼容整数为：

x = 1，因为 abs(2 - 1) = 1 且 2 & 1 = 0。
x = 4，因为 abs(2 - 4) = 2 且 2 & 4 = 0。
x = 5，因为 abs(2 - 5) = 3 且 2 & 5 = 0。

因此，答案为 1 + 4 + 5 = 10。

示例 2：

输入： n = 5, k = 1

输出： 0

解释：

区间 [4, 6] 中没有兼容整数。因此，答案为 0。

提示：

1 <= n <= 100
1 <= k <= 100

解法

方法一：模拟

思考

区间 \([n-k,n+k]\) 长度只有 \(O(k)\)， \(k\le 100\)，枚举每个 \(x\) 判断 \(n\) 与 \(x\) 按位与是否为 \(0\) 即可。为 \(0\) 则累加 \(x\)，下界与 \(1\) 取最大以免非正数。

无需更复杂的数位讨论。

我们在 \([\max(1, n - k), n + k]\) 的范围内枚举 \(x\)，如果 \(n\) 与 \(x\) 的按位与结果为 \(0\)，则将 \(x\) 累加到答案中。

枚举结束后，返回答案即可。

时间复杂度 \(O(k)\)，空间复杂度 \(O(1)\)。

Python3JavaC++GoTypeScript

class Solution:
    def sumOfGoodIntegers(self, n: int, k: int) -> int:
        ans = 0
        for x in range(max(1, n - k), n + k + 1):
            if (n & x) == 0:
                ans += x
        return ans

class Solution {
    public int sumOfGoodIntegers(int n, int k) {
        int ans = 0;
        int start = Math.max(1, n - k);
        int end = n + k;
        for (int x = start; x <= end; x++) {
            if ((n & x) == 0) {
                ans += x;
            }
        }
        return ans;
    }
}

class Solution {
public:
    int sumOfGoodIntegers(int n, int k) {
        int ans = 0;
        int start = max(1, n - k);
        int end = n + k;
        for (int x = start; x <= end; ++x) {
            if ((n & x) == 0) {
                ans += x;
            }
        }
        return ans;
    }
};

func sumOfGoodIntegers(n int, k int) (ans int) {
    start := max(1, n-k)
    end := n + k
    for x := start; x <= end; x++ {
        if (n & x) == 0 {
            ans += x
        }
    }
    return
}

function sumOfGoodIntegers(n: number, k: number): number {
    let ans = 0;
    const start = Math.max(1, n - k);
    const end = n + k;
    for (let x = start; x <= end; x++) {
        if ((n & x) === 0) {
            ans += x;
        }
    }
    return ans;
}

3954. 区间内的兼容数字之和 I

题目描述

解法

方法一：模拟

评论