Facebook Pixel

3954. Sum of Compatible Numbers in Range I

EasyBit ManipulationDynamic ProgrammingEnumeration
LeetCode ↗

Problem 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

Your task is to return the sum of all compatible integers x.

In other words, you need to find every positive integer x whose absolute difference from n is at most k, and which shares no common set bits with n (meaning the bitwise AND of n and x equals 0). Once all such integers are identified, add them together and return the total.

Note:

  • Here, & denotes the bitwise AND operator.
  • The absolute difference between integers i and j is defined as abs(i - j).
Quick Interview Experience
Help others by sharing your interview experience
Have you seen this problem before?

How We Pick the Algorithm

Why Dynamic Programming?

This problem maps to Dynamic Programming through a short path in the full flowchart.

Computemax/min?yesSplit intosubproblems?yesDynamicProgramming

The optimal solution decomposes into overlapping subproblems solved with DP.

Open in Flowchart

Intuition

The key observation is that the condition abs(n - x) <= k limits the possible values of x to a small, continuous range. Since the absolute difference between n and x cannot exceed k, every valid x must lie within the interval [n - k, n + k].

Because x must be a positive integer, the lower bound of this range is actually max(1, n - k), ensuring we never consider zero or negative values.

With this bounded range in hand, we no longer need any clever bit manipulation to enumerate candidates. We can simply iterate through every integer x from max(1, n - k) to n + k, and for each one, check whether it satisfies the second condition (n & x) == 0. This bitwise check confirms that n and x share no common set bits.

Whenever both conditions are met, we add x to our running total. After checking every value in the range, the accumulated sum is the answer. This direct simulation works efficiently here precisely because k keeps the search space small.

Pattern Learn more about Dynamic Programming patterns.

Solution Approach

We use a straightforward simulation strategy, directly translating the two conditions into code.

Step 1: Initialize the answer.

We start with a variable ans = 0 that will accumulate the sum of all compatible integers.

Step 2: Determine the iteration range.

Since every compatible x must satisfy abs(n - x) <= k, the valid candidates fall within the range [n - k, n + k]. Because x must be a positive integer, we clamp the lower bound to max(1, n - k). We then iterate through each value x from max(1, n - k) to n + k inclusive, which in Python is written as:

for x in range(max(1, n - k), n + k + 1):

Step 3: Check the bitwise condition.

For each x in the range, we verify the second condition (n & x) == 0. This bitwise AND check ensures that n and x have no overlapping set bits. If the condition holds, we add x to ans:

if (n & x) == 0:
    ans += x

Step 4: Return the result.

After the loop finishes scanning the entire range, ans holds the sum of all compatible integers, which we return.

Complexity Analysis:

  • Time Complexity: O(k), since we iterate over a range whose size is proportional to k (specifically up to 2k + 1 values), and each bitwise check takes constant time.
  • Space Complexity: O(1), as we only use a single accumulator variable regardless of the input size.

Example Walkthrough

Let's trace through the solution with a small example: n = 4 and k = 3.

Step 1: Initialize the answer.

We set ans = 0.

Step 2: Determine the iteration range.

We need every x satisfying abs(4 - x) <= 3, so x lies in [4 - 3, 4 + 3] = [1, 7]. Since the lower bound max(1, 4 - 3) = max(1, 1) = 1 is already positive, our range is 1 through 7 inclusive.

Note that n = 4 in binary is 100.

Step 3: Check the bitwise condition for each x.

We iterate over each candidate and test (4 & x) == 0:

xbinary4 & x(4 & x) == 0?Action
1001000 = 0✅ Yesans += 1ans = 1
2010000 = 0✅ Yesans += 2ans = 3
3011000 = 0✅ Yesans += 3ans = 6
4100100 = 4❌ Noskip
5101100 = 4❌ Noskip
6110100 = 4❌ Noskip
7111100 = 4❌ Noskip

The values 1, 2, and 3 all have a 0 in the bit position where 4 has its only set bit (the third bit), so they share no common set bits with 4. The values 4 through 7 all keep that third bit set, so their AND with 4 is non-zero and they are excluded.

Step 4: Return the result.

After scanning the full range, the accumulated sum is:

ans = 1 + 2 + 3 = 6

So for n = 4 and k = 3, the function returns 6.

This walkthrough demonstrates the core idea: the k constraint bounds the search to the small window [1, 7], and a simple bitwise AND check on each candidate cleanly filters out any x that overlaps with n's set bits.

Solution Implementation

1class Solution:
2    def sumOfGoodIntegers(self, n: int, k: int) -> int:
3        # Accumulator for the sum of all valid "good" integers
4        total_sum = 0
5
6        # Iterate over candidate integers in the window [n - k, n + k].
7        # max(1, n - k) ensures we never go below 1 (the lower bound stays positive).
8        lower_bound = max(1, n - k)
9        upper_bound = n + k + 1  # +1 because range() is exclusive on the upper end
10
11        for candidate in range(lower_bound, upper_bound):
12            # A candidate is "good" only if it shares no common set bits with n.
13            # (n & candidate) == 0 means the binary representations are disjoint.
14            if (n & candidate) == 0:
15                total_sum += candidate
16
17        return total_sum
18
1class Solution {
2    /**
3     * Computes the sum of all "good" integers within a bounded range around n.
4     * An integer x is considered "good" if it shares no common set bits with n,
5     * i.e. (n & x) == 0.
6     *
7     * @param n the reference number used for both range computation and bit check
8     * @param k the range radius used to derive the inclusive search bounds
9     * @return  the accumulated sum of every good integer in [start, end]
10     */
11    public int sumOfGoodIntegers(int n, int k) {
12        // Running total of all good integers found.
13        int sum = 0;
14
15        // Lower bound of the search range, clamped to a minimum of 1.
16        int start = Math.max(1, n - k);
17
18        // Upper bound of the search range (inclusive).
19        int end = n + k;
20
21        // Iterate over every candidate value in the inclusive range [start, end].
22        for (int x = start; x <= end; x++) {
23            // x is "good" only when it has no overlapping set bits with n.
24            if ((n & x) == 0) {
25                sum += x;
26            }
27        }
28
29        return sum;
30    }
31}
32
1class Solution {
2public:
3    int sumOfGoodIntegers(int n, int k) {
4        // Accumulator for the sum of all "good" integers found in the range.
5        int sum = 0;
6
7        // Define the lower bound of the search range.
8        // We never go below 1, hence the use of max(1, ...).
9        int rangeStart = max(1, n - k);
10
11        // Define the upper bound of the search range.
12        int rangeEnd = n + k;
13
14        // Iterate over every integer within the inclusive range [rangeStart, rangeEnd].
15        for (int candidate = rangeStart; candidate <= rangeEnd; ++candidate) {
16            // A candidate is considered "good" when it shares no set bits with n,
17            // i.e. the bitwise AND of n and candidate equals 0.
18            if ((n & candidate) == 0) {
19                // Add the qualifying candidate to the running total.
20                sum += candidate;
21            }
22        }
23
24        // Return the total sum of all good integers.
25        return sum;
26    }
27};
28
1/**
2 * Computes the sum of all "good" integers within a range determined by n and k.
3 *
4 * An integer x is considered "good" if it lies within the inclusive range
5 * [max(1, n - k), n + k] and shares no common set bits with n
6 * (i.e. the bitwise AND of n and x equals 0).
7 *
8 * @param n - The base integer used for range calculation and the bitwise check.
9 * @param k - The offset that defines the width of the search range around n.
10 * @returns The sum of every integer in the range that satisfies the bitwise condition.
11 */
12function sumOfGoodIntegers(n: number, k: number): number {
13    // Accumulator for the running total of all qualifying integers.
14    let answer = 0;
15
16    // Lower bound of the search range; clamped to at least 1 so we never go below 1.
17    const start = Math.max(1, n - k);
18
19    // Upper bound of the search range.
20    const end = n + k;
21
22    // Iterate over every candidate integer in the inclusive range [start, end].
23    for (let x = start; x <= end; x++) {
24        // A candidate qualifies only if it has no bits in common with n.
25        if ((n & x) === 0) {
26            answer += x;
27        }
28    }
29
30    return answer;
31}
32

Time and Space Complexity

  • Time Complexity: O(k)

    The core of the function is a single for loop iterating over range(max(1, n - k), n + k + 1). The number of iterations depends on the span of this range. The lower bound is max(1, n - k) and the upper bound is n + k + 1. In the typical case where n - k >= 1, the range spans from n - k to n + k, giving approximately 2k + 1 iterations. Thus the loop executes on the order of k times. Inside the loop, each operation—the bitwise and (n & x), the comparison, and the addition—runs in constant time O(1). Therefore, the overall time complexity is O(k).

  • Space Complexity: O(1)

    The algorithm uses only a fixed number of auxiliary variables (ans and the loop variable x), and range in Python produces values lazily without materializing a list. No additional data structures grow with the input size, so the space complexity is constant O(1).

Pattern Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Forgetting the positive-integer lower bound (x must be ≥ 1).

A very common mistake is iterating directly from n - k without clamping the lower bound. When k >= n, the value n - k becomes zero or negative. This causes two problems:

  • Including 0: When x = 0, the condition (n & 0) == 0 is always True, so 0 would pass the bitwise check. Although adding 0 doesn't change the sum, it violates the positive integer requirement and signals a logical error.
  • Including negative numbers: For negative x, Python represents integers using a conceptually infinite two's-complement form, so (n & x) may behave unexpectedly and incorrectly mark some negatives as "compatible." These would then corrupt the sum.
# WRONG: may include 0 and negative numbers when k >= n
for x in range(n - k, n + k + 1):
    if (n & x) == 0:
        ans += x

# CORRECT: clamp the lower bound to 1
for x in range(max(1, n - k), n + k + 1):
    if (n & x) == 0:
        ans += x

Pitfall 2: Off-by-one error on the upper bound.

The condition is abs(n - x) <= k, which means x = n + k is a valid candidate (inclusive). Because Python's range() is exclusive on its upper end, you must write n + k + 1. Forgetting the + 1 silently drops the largest candidate n + k, producing a result that is too small whenever that boundary value happens to be compatible.

# WRONG: misses x = n + k
for x in range(max(1, n - k), n + k):
    ...

# CORRECT: include n + k by adding 1
for x in range(max(1, n - k), n + k + 1):
    ...

Pitfall 3: Misreading the AND condition as "must share bits."

The requirement (n & x) == 0 means n and x have no overlapping set bits (disjoint binary representations). It's easy to accidentally flip the logic and write if (n & x) != 0 or if n & x, which would sum exactly the wrong set of integers. Always double-check that you are accumulating values where the AND equals zero.

# WRONG: this selects integers that SHARE bits with n
if (n & x) != 0:
    ans += x

# CORRECT: select integers with no common set bits
if (n & x) == 0:
    ans += x

Pitfall 4: Including n itself without realizing it is naturally excluded.

One might worry whether x = n (always within the range since abs(n - n) = 0 <= k) should be filtered out separately. There's no need: for any n > 0, (n & n) == n != 0, so n automatically fails the bitwise check and is never added. However, the special case n = 0 deserves attention—if the problem ever allows n = 0, then (0 & x) == 0 holds for every x, and the logic would sum the entire window. Confirm the constraints to know whether this edge case can occur.

Ready to land your dream job?

Unlock your dream job with a 5-minute quiz for a personalized study roadmap!

Get My Roadmap
Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Get a Personalized Study Roadmap:

Which technique can we use to find the middle of a linked list?


Recommended Readings

Want a Structured Path to Master System Design Too? Don’t Miss This!

Load More