Count Pairs with Given Sum and XOR

Problem

Given integers M and N, write a program that counts how many positive integer pairs (a, b) satisfy the following conditions:

a + b = M
a XOR b = N

Examples

Example 1

1
2
3
4
5
6
7


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

1
2
3
4
5
6
7


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

1
2
3
4
5
6


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

1
2
3
4
5


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

1
2
3
4
5
6


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 = M and a 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) / 2 and xorVal = N
For valid pairs to exist, andVal & xorVal must be 0 (no overlapping bits)
If valid, the number of pairs depends on the number of bits set in xorVal
Each bit position in xorVal allows 2 choices for distributing bits between a and b
Total pairs = 2^(number of set bits in xorVal)
Filter out pairs where either a or b is non-positive

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46


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;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54


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
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47


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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38


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) / 2 and verify no bit overlap with N
Handle special case: if N = 0, return 1 if M > 0 and M is even, else 0
For N > 0, calculate total theoretical pairs as 2^(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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34


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
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34


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
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33


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
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27


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 a from 1 to M-1
For each a, calculate b = 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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


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;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


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
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


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

Problem#

Examples#

Example 1#

Example 2#

Example 3#

Example 4#

Example 5#

Solution#

Method 1 - Mathematical Bit Manipulation Analysis#

Intuition#

Approach#

Code#

Complexity#

Method 2 - Direct Mathematical Calculation#

Intuition#

Approach#

Code#

Complexity#

Method 3 - Brute Force Enumeration#

Intuition#

Approach#

Code#

Complexity#

Notes#

Problem

Examples

Example 1

Example 2

Example 3

Example 4

Example 5

Solution

Method 1 - Mathematical Bit Manipulation Analysis

Intuition

Approach

Code

Complexity

Method 2 - Direct Mathematical Calculation

Intuition

Approach

Code

Complexity

Method 3 - Brute Force Enumeration

Intuition

Approach

Code

Complexity

Notes