Welcome to Subscribe On Youtube

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

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)$.

  • 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;
    }
};

  • 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


  • 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;
}

All Problems

All Solutions