跳转至

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

题目描述

给你两个整数 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

解法

方法一：模拟

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

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

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

1
2
3
4
5
6
7
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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
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;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
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
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
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;
}

评论