Count Pairs with Given Sum and XOR
EasyUpdated: Aug 10, 2025
Problem
Given integers M and N, write a program that counts how many positive integer pairs (a, b) satisfy the following conditions:
a + b = Ma XOR b = N
Examples
Example 1
Input: M = 9, N = 5
Output: 2
Explanation:
The pairs that satisfy both conditions are:
- (2, 7): 2 + 7 = 9, 2 XOR 7 = 5 ✓
- (7, 2): 7 + 2 = 9, 7 XOR 2 = 5 ✓
Since we need positive integers, both pairs are valid.
Example 2
Input: M = 6, N = 2
Output: 2
Explanation:
The pairs that satisfy both conditions are:
- (2, 4): 2 + 4 = 6, 2 XOR 4 = 2 ✓
- (4, 2): 4 + 2 = 6, 4 XOR 2 = 2 ✓
Both pairs contain positive integers.
Example 3
Input: M = 4, N = 0
Output: 1
Explanation:
The only pair is:
- (2, 2): 2 + 2 = 4, 2 XOR 2 = 0 ✓
Only one valid pair exists.
Example 4
Input: M = 3, N = 5
Output: 0
Explanation:
No positive integer pairs can satisfy both conditions.
For a + b = 3 and a XOR b = 5, we would need negative values.
Example 5
Input: M = 10, N = 2
Output: 2
Explanation:
The pairs that satisfy both conditions are:
- (4, 6): 4 + 6 = 10, 4 XOR 6 = 2 ✓
- (6, 4): 6 + 4 = 10, 6 XOR 4 = 2 ✓
Solution
Method 1 - Mathematical Bit Manipulation Analysis
Intuition
We can use the mathematical relationship between addition and XOR. For any two numbers a and b: a + b = (a XOR b) + 2 * (a AND b). Given that a + b = M and a XOR b = N, we can derive a AND b = (M - N) / 2. If this value is non-negative and integer, we can check if valid pairs exist using bit manipulation properties.
Approach
- Use the identity:
a + b = (a XOR b) + 2 * (a AND b) - Given
a + b = Manda XOR b = N, derive:a AND b = (M - N) / 2 - Check if
(M - N)is even and non-negative (required for valid AND value) - Let
andVal = (M - N) / 2andxorVal = N - For valid pairs to exist,
andVal & xorValmust be 0 (no overlapping bits) - If valid, the number of pairs depends on the number of bits set in
xorVal - Each bit position in
xorValallows 2 choices for distributing bits between a and b - Total pairs =
2^(number of set bits in xorVal) - Filter out pairs where either
aorbis non-positive
Code
C++
class Solution {
public:
int countPairs(int M, int N) {
// Check if (M - N) is even and non-negative
if ((M - N) % 2 != 0 || M - N < 0) {
return 0;
}
int andVal = (M - N) / 2;
int xorVal = N;
// Check if andVal and xorVal have overlapping bits
if ((andVal & xorVal) != 0) {
return 0;
}
// Count set bits in xorVal
int setBits = __builtin_popcount(xorVal);
int totalPairs = 1 << setBits; // 2^setBits
// Check each possible pair and count valid ones
int validPairs = 0;
for (int i = 0; i < totalPairs; i++) {
int a = andVal;
int b = andVal;
// Distribute XOR bits
for (int bit = 0; bit < 32; bit++) {
if ((xorVal >> bit) & 1) {
if ((i >> __builtin_popcount(xorVal & ((1 << bit) - 1))) & 1) {
a |= (1 << bit);
} else {
b |= (1 << bit);
}
}
}
if (a > 0 && b > 0) {
validPairs++;
}
}
return validPairs;
}
};
Go
func countPairs(M, N int) int {
// Check if (M - N) is even and non-negative
if (M-N)%2 != 0 || M-N < 0 {
return 0
}
andVal := (M - N) / 2
xorVal := N
// Check if andVal and xorVal have overlapping bits
if (andVal & xorVal) != 0 {
return 0
}
// Count set bits in xorVal
setBits := popcount(xorVal)
totalPairs := 1 << setBits // 2^setBits
// Check each possible pair and count valid ones
validPairs := 0
for i := 0; i < totalPairs; i++ {
a := andVal
b := andVal
// Distribute XOR bits
bitIdx := 0
for bit := 0; bit < 32; bit++ {
if (xorVal>>bit)&1 == 1 {
if (i>>bitIdx)&1 == 1 {
a |= (1 << bit)
} else {
b |= (1 << bit)
}
bitIdx++
}
}
if a > 0 && b > 0 {
validPairs++
}
}
return validPairs
}
func popcount(x int) int {
count := 0
for x > 0 {
count += x & 1
x >>= 1
}
return count
}
Java
class Solution {
public int countPairs(int M, int N) {
// Check if (M - N) is even and non-negative
if ((M - N) % 2 != 0 || M - N < 0) {
return 0;
}
int andVal = (M - N) / 2;
int xorVal = N;
// Check if andVal and xorVal have overlapping bits
if ((andVal & xorVal) != 0) {
return 0;
}
// Count set bits in xorVal
int setBits = Integer.bitCount(xorVal);
int totalPairs = 1 << setBits; // 2^setBits
// Check each possible pair and count valid ones
int validPairs = 0;
for (int i = 0; i < totalPairs; i++) {
int a = andVal;
int b = andVal;
// Distribute XOR bits
int bitIdx = 0;
for (int bit = 0; bit < 32; bit++) {
if ((xorVal >> bit & 1) == 1) {
if ((i >> bitIdx & 1) == 1) {
a |= (1 << bit);
} else {
b |= (1 << bit);
}
bitIdx++;
}
}
if (a > 0 && b > 0) {
validPairs++;
}
}
return validPairs;
}
}
Python
class Solution:
def count_pairs(self, M: int, N: int) -> int:
# Check if (M - N) is even and non-negative
if (M - N) % 2 != 0 or M - N < 0:
return 0
and_val = (M - N) // 2
xor_val = N
# Check if and_val and xor_val have overlapping bits
if (and_val & xor_val) != 0:
return 0
# Count set bits in xor_val
set_bits = bin(xor_val).count('1')
total_pairs = 1 << set_bits # 2^set_bits
# Check each possible pair and count valid ones
valid_pairs = 0
for i in range(total_pairs):
a = and_val
b = and_val
# Distribute XOR bits
bit_idx = 0
for bit in range(32):
if (xor_val >> bit) & 1:
if (i >> bit_idx) & 1:
a |= (1 << bit)
else:
b |= (1 << bit)
bit_idx += 1
if a > 0 and b > 0:
valid_pairs += 1
return valid_pairs
Complexity
- ⏰ Time complexity:
O(2^k), where k is the number of set bits in N. We generate all possible pairs and validate each - 🧺 Space complexity:
O(1), only using constant extra space for calculations
Method 2 - Direct Mathematical Calculation
Intuition
We can directly calculate the result without generating all pairs. After verifying that valid pairs can exist using the mathematical constraints, we check the boundary conditions. If N = 0, there's exactly one pair (M/2, M/2) if M is even. Otherwise, we have 2^k total combinations, but we need to subtract cases where either number becomes zero or negative.
Approach
- Validate basic constraints:
(M - N)must be even and non-negative - Calculate
andVal = (M - N) / 2and verify no bit overlap with N - Handle special case: if
N = 0, return 1 ifM > 0andMis even, else 0 - For
N > 0, calculate total theoretical pairs as2^(set bits in N) - Check boundary conditions:
- Minimum possible value for a or b is when all XOR bits go to the other number
- If minimum value ≤ 0, subtract invalid cases
- Count valid pairs directly using mathematical analysis
Code
C++
class Solution {
public:
int countPairsDirect(int M, int N) {
// Basic validation
if ((M - N) % 2 != 0 || M - N < 0) {
return 0;
}
int andVal = (M - N) / 2;
// Check bit overlap
if ((andVal & N) != 0) {
return 0;
}
// Special case: N = 0
if (N == 0) {
return (M > 0 && M % 2 == 0) ? 1 : 0;
}
// Calculate minimum possible values
int minA = andVal; // When all XOR bits go to b
int minB = andVal; // When all XOR bits go to a
// Both must be positive
if (minA <= 0 || minB <= 0) {
return 0;
}
// Count set bits in N
int setBits = __builtin_popcount(N);
return 1 << setBits; // 2^setBits
}
};
Go
func countPairsDirect(M, N int) int {
// Basic validation
if (M-N)%2 != 0 || M-N < 0 {
return 0
}
andVal := (M - N) / 2
// Check bit overlap
if (andVal & N) != 0 {
return 0
}
// Special case: N = 0
if N == 0 {
if M > 0 && M%2 == 0 {
return 1
}
return 0
}
// Calculate minimum possible values
minA := andVal // When all XOR bits go to b
minB := andVal // When all XOR bits go to a
// Both must be positive
if minA <= 0 || minB <= 0 {
return 0
}
// Count set bits in N
setBits := popcount(N)
return 1 << setBits // 2^setBits
}
Java
class Solution {
public int countPairsDirect(int M, int N) {
// Basic validation
if ((M - N) % 2 != 0 || M - N < 0) {
return 0;
}
int andVal = (M - N) / 2;
// Check bit overlap
if ((andVal & N) != 0) {
return 0;
}
// Special case: N = 0
if (N == 0) {
return (M > 0 && M % 2 == 0) ? 1 : 0;
}
// Calculate minimum possible values
int minA = andVal; // When all XOR bits go to b
int minB = andVal; // When all XOR bits go to a
// Both must be positive
if (minA <= 0 || minB <= 0) {
return 0;
}
// Count set bits in N
int setBits = Integer.bitCount(N);
return 1 << setBits; // 2^setBits
}
}
Python
class Solution:
def count_pairs_direct(self, M: int, N: int) -> int:
# Basic validation
if (M - N) % 2 != 0 or M - N < 0:
return 0
and_val = (M - N) // 2
# Check bit overlap
if (and_val & N) != 0:
return 0
# Special case: N = 0
if N == 0:
return 1 if M > 0 and M % 2 == 0 else 0
# Calculate minimum possible values
min_a = and_val # When all XOR bits go to b
min_b = and_val # When all XOR bits go to a
# Both must be positive
if min_a <= 0 or min_b <= 0:
return 0
# Count set bits in N
set_bits = bin(N).count('1')
return 1 << set_bits # 2^set_bits
Complexity
- ⏰ Time complexity:
O(log N), for counting set bits in N - 🧺 Space complexity:
O(1), only using constant extra space
Method 3 - Brute Force Enumeration
Intuition
A straightforward approach is to iterate through all possible values of a from 1 to M-1, calculate b = M - a, and check if both conditions are satisfied. This method is simple to understand and implement, though not optimal for large values.
Approach
- Iterate through all possible values of
afrom 1 to M-1 - For each
a, calculateb = M - a - Check if
b > 0(positive integer constraint) - Verify if
a XOR b = N - Count all valid pairs that satisfy both conditions
- Handle edge cases where M ≤ 1
Code
C++
class Solution {
public:
int countPairsBrute(int M, int N) {
if (M <= 1) return 0;
int count = 0;
for (int a = 1; a < M; a++) {
int b = M - a;
if (b > 0 && (a ^ b) == N) {
count++;
}
}
return count;
}
};
Go
func countPairsBrute(M, N int) int {
if M <= 1 {
return 0
}
count := 0
for a := 1; a < M; a++ {
b := M - a
if b > 0 && (a^b) == N {
count++
}
}
return count
}
Java
class Solution {
public int countPairsBrute(int M, int N) {
if (M <= 1) return 0;
int count = 0;
for (int a = 1; a < M; a++) {
int b = M - a;
if (b > 0 && (a ^ b) == N) {
count++;
}
}
return count;
}
}
Python
class Solution:
def count_pairs_brute(self, M: int, N: int) -> int:
if M <= 1:
return 0
count = 0
for a in range(1, M):
b = M - a
if b > 0 and (a ^ b) == N:
count += 1
return count
Complexity
- ⏰ Time complexity:
O(M), where M is the target sum. We iterate through all possible values of a - 🧺 Space complexity:
O(1), only using constant extra space
Notes
- Method 2 provides the most efficient solution with O(log N) time complexity
- Method 1 offers detailed bit manipulation analysis but has exponential time in worst case
- Method 3 is useful for verification and understanding the problem constraints
- The key insight is using the mathematical relationship:
a + b = (a XOR b) + 2 * (a AND b) - Edge cases include when no valid pairs exist due to mathematical constraints
- The problem combines number theory with bit manipulation techniques
- For large inputs, Method 2 is recommended due to its optimal time complexity