Is Sum of Compatible Numbers in Range I easy or hard?

The problem is typically classified as Easy because the main logic relies on a single compatibility check using bitwise AND. The challenge comes from recognizing that compatibility is determined by shared bits and then implementing the range scan efficiently.

Sum of Compatible Numbers in Range I Python/Java solution

In Python or Java, the core logic is a loop that checks the compatibility condition using the bitwise AND operator. If (num & target) == 0, add the number to the running sum. Both languages support efficient bit operations, so the implementation remains straightforward and runs in O(n) time.

How to solve Sum of Compatible Numbers in Range I in O(n)?

Iterate through the range once and check compatibility using the bitwise condition (num & target) == 0. Maintain a running sum for all numbers that satisfy the condition. Since each check is constant time, the full pass over n numbers results in O(n) time and O(1) extra space.

What is the best approach for Sum of Compatible Numbers in Range I?

The best approach depends on input size. A brute force scan works in O(n) time and is often acceptable for small ranges. For larger inputs or repeated queries, precomputing sums by bitmask or using subset enumeration reduces repeated compatibility checks and significantly improves performance.

Is Sum of Compatible Numbers in Range I asked at Google/Amazon/Meta?

Bit manipulation and compatibility checks using bitwise AND frequently appear in interviews at companies like Google, Amazon, and Meta. Variants involving subset masks or compatible bit patterns are common because they test understanding of low‑level operations and optimization strategies.

What data structure is used in Sum of Compatible Numbers in Range I?

The basic solution only needs simple variables for iteration and summation. Optimized solutions often use hash maps or arrays indexed by bitmask to store counts or sums of numbers, enabling faster compatibility lookups.

What is the time complexity of Sum of Compatible Numbers in Range I?

The straightforward solution runs in O(n) time because each number in the range is checked with a constant‑time bitwise AND operation. Optimized approaches using bitmask preprocessing or subset enumeration can reduce repeated work, often achieving near O(1) query time after preprocessing.

Description Hints 3 Solution Video 2:47

3954. Sum of Compatible Numbers in Range I

Easy58.4% acceptance

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

Topics

Hints open one at a time

Hint 1

The condition abs(n - x) <= k means x is in the range [n - k, n + k].

Hint 2

Since x must be positive, start checking from max(1, n - k).

Hint 3

Iterate through all values in this range and add x to the answer when (n & x) == 0.

2:47

Still stuck?Read the written solution, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def sumOfGoodIntegers(self, n: int, k: int) -> int:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2

Input

2
3

Input

5
1

Your code is saved on this device.Solution