Skip to content

3954. Sum of Compatible Numbers in Range I

Description

You are given two integers n and k.

A positive integer x is called compatible if it satisfies both of the following conditions:

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

Return the sum of all compatible integers x.

Note:

  • Here, & denotes the bitwise AND operator.
  • The absolute difference between integers i and j is defined as abs(i - j).

 

Example 1:

Input: n = 2, k = 3

Output: 10

Explanation:

The compatible integers are:

  • x = 1, since abs(2 - 1) = 1 and 2 & 1 = 0.
  • x = 4, since abs(2 - 4) = 2 and 2 & 4 = 0.
  • x = 5, since abs(2 - 5) = 3 and 2 & 5 = 0.

Thus, the answer is 1 + 4 + 5 = 10.

Example 2:

Input: n = 5, k = 1

Output: 0

Explanation:

There are no compatible integers in the range [4, 6]. Thus, the answer is 0.

 

Constraints:

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

Solutions

Solution 1: Simulation

Thinking

The interval \([n-k,n+k]\) has length \(O(k)\) and \(k\le 100\), so we test \(n\&x=0\) for each \(x\) and add the hits. The left end is clamped at \(1\) to skip non-positive integers.

No digit-DP is required.

We iterate through \(x\) within the range \([\max(1, n - k), n + k]\). If the bitwise AND result of \(n\) and \(x\) is \(0\), we accumulate \(x\) into the answer.

After the iteration ends, simply return the answer.

The time complexity is \(O(k)\), and the space complexity is \(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;
}

Comments