Sum of Compatible Numbers in Range I - Video Solutions
3954. Sum of Compatible Numbers in Range I (Leetcode Easy)
Sum of Compatible Numbers in Range I - Video Solution
Watch 5 video solutions for Sum of Compatible Numbers in Range I, a easy level problem involving Dynamic Programming, Bit Manipulation, Enumeration. This walkthrough by Programming Live with Larry has 203 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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
iandjis defined asabs(i - j).
Example 1:
Input: n = 2, k = 3
Output: 10
Explanation:
The compatible integers are:
x = 1, sinceabs(2 - 1) = 1and2 & 1 = 0.x = 4, sinceabs(2 - 4) = 2and2 & 4 = 0.x = 5, sinceabs(2 - 5) = 3and2 & 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 <= 1001 <= 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.
Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Range Scan | O(n) | O(1) | Small ranges or single query where simplicity matters |
| Hash Map / Frequency by Bitmask | O(n) preprocessing + O(m) mask checks | O(n) | Multiple queries or repeated compatibility checks |
| Bitmask Subset Enumeration | O(2^b) | O(2^b) | When bit width is small and compatibility depends on bit patterns |