Skip to main content
Talentd

Sum of Compatible Numbers in Range I - Solution & Explanation

EasyDynamic ProgrammingBit ManipulationEnumeration6 min read
Practice this problem

Problem Statement

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

Approach Overview

Problem Overview: You are given numbers and a range constraint. A number is considered compatible with another if their bit representations do not conflict (commonly checked using (a & b) == 0). The task is to compute the sum of numbers within a given range that satisfy this compatibility rule.

Approach 1: Brute Force Scan (O(n) time, O(1) space)

The most direct solution iterates through every number in the specified range and checks compatibility using a bitwise AND operation. If (num & target) == 0, the number is compatible and contributes to the running sum. This approach relies only on a simple loop and a constant‑time bit operation. It works well when the range size is small, but performance degrades when the range grows large because every candidate must be evaluated individually.

Approach 2: Precompute Compatible Masks with Frequency Map (O(n) preprocessing, near O(1) query)

When the input contains many numbers or repeated queries, you can precompute counts or sums of numbers by their bitmask representation. Store the frequency or sum of each mask in a hash map or array indexed by mask. For a given target mask, any compatible number must satisfy (mask & target) == 0. Iterating through stored masks and summing those that satisfy the condition avoids rescanning the entire range repeatedly. Hash lookups make this significantly faster in practice.

Approach 3: Bitmask Subset Enumeration (O(2^b) time, O(2^b) space)

If the number of bits b is small (for example ≤20), build a table storing the sum of numbers for each bitmask. Instead of checking every value directly, enumerate all masks that are subsets of the complement of the target mask. Each valid subset automatically satisfies the compatibility condition. This technique appears often in bitmask and bit manipulation problems where compatibility constraints depend on shared bits.

Recommended for interviews: Start with the brute force scan because it clearly demonstrates the compatibility condition and the use of (a & b). Then move to the bitmask or frequency‑based optimization. Interviewers typically expect you to recognize that compatibility is a bitwise property and that precomputing masks or using subset enumeration can reduce repeated work.

Solution

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

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Range ScanO(n)O(1)Small ranges or single query where simplicity matters
Hash Map / Frequency by BitmaskO(n) preprocessing + O(m) mask checksO(n)Multiple queries or repeated compatibility checks
Bitmask Subset EnumerationO(2^b)O(2^b)When bit width is small and compatibility depends on bit patterns

Video Solution

3954. Sum of Compatible Numbers in Range I (Leetcode Easy) • Programming Live with Larry • 203 views views

Watch 4 more video solutions →

Frequently Asked Questions

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.

Ready to solve this problem?

Practice Sum of Compatible Numbers in Range I with our built-in code editor and test cases.

Practice on FleetCode
Previous

Longest Palindromic Substring

Next

Regular Expression Matching