# Count ordered pairs of positive numbers such that their sum is S and XOR is K

Given a sum and a number . The task is to count all possible ordered pairs **(a, b)** of positive numbers such that the two positive integers **a** and **b** have a sum of **S** and a bitwise-XOR of **K**.**Examples**:

Input: S = 9, K = 5Output: 4 The ordered pairs are (2, 7), (3, 6), (6, 3), (7, 2)Input: S = 2, K = 2Output: 0 There are no such ordered pair.

Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the **DSA Self Paced Course** at a student-friendly price and become industry ready. To complete your preparation from learning a language to DS Algo and many more, please refer **Complete Interview Preparation Course****.**

In case you wish to attend **live classes **with experts, please refer **DSA Live Classes for Working Professionals **and **Competitive Programming Live for Students**.

**Approach: **

For any two integers and ,

Sum

S = a + bcan be written as S = (a b) + (a & b)*2

Where a b is the bitwise XOR and a & b is bitwise AND of the two number a and b respectively.

This is because is non-carrying binary addition. Thus we can write **a & b = (S-K)/2** where **S=(a + b)** and **K = (a **

*** QuickLaTeX cannot compile formula: *** Error message: Error: Nothing to show, formula is empty

**b)**.

If (S-K) is odd or (S-K) less than 0,

- then there is no such ordered pair.

**Now, for each bit**, a&b {0, 1} and (a b){0, 1}.

- If, (a b) = 0 then a
_{i}= b_{i}, so we have one possibility: a_{i}= b_{i}= (a_{i}& b_{i}). - If, (a b) = 1 then we must have (a
_{i}& b_{i}) = 0 (otherwise the output is 0), and we have two choices: either (a_{i}= 1 and b_{i}= 0) or (a_{i}= 0 and b_{i}= 1).

Where a_{i} is the i-th bit in a and b_{i} is the i-th bit in b.

Thus, the answer is 2, where is the number of set bits in K.

We will subtract 2 if S and K are equal because a and b must be positive(>0).

Below is the implementation of the above approach:

## C++

`// C++ program to count ordered pairs of` `// positive numbers such that their` `// sum is S and XOR is K` `#include <bits/stdc++.h>` `using` `namespace` `std;` `// Function to count ordered pairs of` `// positive numbers such that their` `// sum is S and XOR is K` `int` `countPairs(` `int` `s, ` `int` `K)` `{` ` ` `// Check if no such pair exists` ` ` `if` `(K > s || (s - K) % 2) {` ` ` `return` `0;` ` ` `}` ` ` `if` `((s - K) / 2 & K) {` ` ` `return` `0;` ` ` `}` ` ` `// Calculate set bits in K` ` ` `int` `setBits = __builtin_popcount(K);` ` ` `// Calculate pairs` ` ` `int` `pairsCount = ` `pow` `(2, setBits);` ` ` `// If s = k, subtract 2 from result` ` ` `if` `(s == K)` ` ` `pairsCount -= 2;` ` ` `return` `pairsCount;` `}` `// Driver code` `int` `main()` `{` ` ` `int` `s = 9, K = 5;` ` ` `cout << countPairs(s, K);` ` ` `return` `0;` `}` |

## Java

`// Java program to count ordered pairs of` `// positive numbers such that their` `// sum is S and XOR is K` `class` `GFG {` `// Function to count ordered pairs of` `// positive numbers such that their` `// sum is S and XOR is K` ` ` `static` `int` `countPairs(` `int` `s, ` `int` `K) {` ` ` `// Check if no such pair exists` ` ` `if` `(K > s || (s - K) % ` `2` `==` `1` `) {` ` ` `return` `0` `;` ` ` `}` ` ` `if` `((s - K) / ` `2` `== ` `1` `& K == ` `1` `) {` ` ` `return` `0` `;` ` ` `}` ` ` `// Calculate set bits in K` ` ` `int` `setBits = __builtin_popcount(K);` ` ` `// Calculate pairs` ` ` `int` `pairsCount = (` `int` `) Math.pow(` `2` `, setBits);` ` ` `// If s = k, subtract 2 from result` ` ` `if` `(s == K) {` ` ` `pairsCount -= ` `2` `;` ` ` `}` ` ` `return` `pairsCount;` ` ` `}` ` ` `static` `int` `__builtin_popcount(` `int` `n) {` ` ` `/* Function to get no of set ` ` ` `bits in binary representation ` ` ` `of positive integer n */` ` ` `int` `count = ` `0` `;` ` ` `while` `(n > ` `0` `) {` ` ` `count += n & ` `1` `;` ` ` `n >>= ` `1` `;` ` ` `}` ` ` `return` `count;` ` ` `}` `// Driver program to test above function` ` ` `public` `static` `void` `main(String[] args) {` ` ` `int` `s = ` `9` `, K = ` `5` `;` ` ` `System.out.println(countPairs(s, K));` ` ` `}` `}` |

## Python3

`# Python3 program to count ordered pairs of` `# positive numbers such that their` `# sum is S and XOR is K` `# Function to count ordered pairs of` `# positive numbers such that their` `# sum is S and XOR is K` `def` `countPairs(s,K):` ` ` `if` `(K>s ` `or` `(s` `-` `K)` `%` `2` `=` `=` `1` `):` ` ` `return` `0` ` ` ` ` `# Calculate set bits in k` ` ` `setBits` `=` `(` `str` `(` `bin` `(K))[` `2` `:]).count(` `"1"` `)` ` ` `# Calculate pairs` ` ` `pairsCount ` `=` `pow` `(` `2` `,setBits)` ` ` `# If s = k, subtract 2 from result` ` ` `if` `(s` `=` `=` `K):` ` ` `pairsCount` `-` `=` `2` ` ` `return` `pairsCount` `# Driver code` `if` `__name__` `=` `=` `'__main__'` `:` ` ` `s,K` `=` `9` `,` `5` ` ` `print` `(countPairs(s,K))` `# This code is contributed by` `# Indrajit Sinha.` |

## C#

`// C# program to count ordered pairs` `// of positive numbers such that their` `// sum is S and XOR is K` `using` `System;` ` ` `class` `GFG` `{` `// Function to count ordered pairs of` `// positive numbers such that their` `// sum is S and XOR is K` `static` `int` `countPairs(` `int` `s, ` `int` `K)` `{` ` ` `// Check if no such pair exists` ` ` `if` `(K > s || (s - K) % 2 ==1)` ` ` `{` ` ` `return` `0;` ` ` `}` ` ` `if` `((s - K) / 2 == 1 & K == 1)` ` ` `{` ` ` `return` `0;` ` ` `}` ` ` `// Calculate set bits in K` ` ` `int` `setBits = __builtin_popcount(K);` ` ` `// Calculate pairs` ` ` `int` `pairsCount = (` `int` `) Math.Pow(2, setBits);` ` ` `// If s = k, subtract 2 from result` ` ` `if` `(s == K)` ` ` `{` ` ` `pairsCount -= 2;` ` ` `}` ` ` `return` `pairsCount;` `}` `static` `int` `__builtin_popcount(` `int` `n)` `{` ` ` `/* Function to get no of set` ` ` `bits in binary representation` ` ` `of positive integer n */` ` ` `int` `count = 0;` ` ` `while` `(n > 0)` ` ` `{` ` ` `count += n & 1;` ` ` `n >>= 1;` ` ` `}` ` ` `return` `count;` `}` `// Driver Code` `public` `static` `void` `Main()` `{` ` ` `int` `s = 9, K = 5;` ` ` `Console.Write(countPairs(s, K));` `}` `}` `// This code is contributed` `// by Rajput-Ji` |

## PHP

`<?php` `// PHP program to count ordered` `// pairs of positive numbers such` `// that their sum is S and XOR is K` `// Function to count ordered pairs of` `// positive numbers such that their` `// sum is S and XOR is K` `function` `countPairs(` `$s` `, ` `$K` `)` `{` ` ` `// Check if no such pair exists` ` ` `if` `(` `$K` `> ` `$s` `|| (` `$s` `- ` `$K` `) % 2 == 1)` ` ` `{` ` ` `return` `0;` ` ` `}` ` ` `if` `((` `$s` `- ` `$K` `) / 2 == 1 & ` `$K` `== 1)` ` ` `{` ` ` `return` `0;` ` ` `}` ` ` `// Calculate set bits in K` ` ` `$setBits` `= __builtin_popcount(` `$K` `);` ` ` `// Calculate pairs` ` ` `$pairsCount` `= (int)pow(2, ` `$setBits` `);` ` ` `// If s = k, subtract 2 from result` ` ` `if` `(` `$s` `== ` `$K` `)` ` ` `{` ` ` `$pairsCount` `-= 2;` ` ` `}` ` ` `return` `$pairsCount` `;` `}` `function` `__builtin_popcount(` `$n` `)` `{` ` ` `/* Function to get no of set` ` ` `bits in binary representation` ` ` `of positive integer n */` ` ` `$count` `= 0;` ` ` `while` `(` `$n` `> 0)` ` ` `{` ` ` `$count` `+= ` `$n` `& 1;` ` ` `$n` `>>= 1;` ` ` `}` ` ` `return` `$count` `;` `}` `// Driver Code` `$s` `= 9; ` `$K` `= 5;` `echo` `countPairs(` `$s` `, ` `$K` `) . ` `"\n"` `;` `// This code is contributed` `// by Akanksha Rai` |

## Javascript

`<script>` `// Javascript program to count ordered pairs of` `// positive numbers such that their` `// sum is S and XOR is K` `// Function to count ordered pairs of` `// positive numbers such that their` `// sum is S and XOR is K` `function` `countPairs(s, K)` `{` ` ` `// Check if no such pair exists` ` ` `if` `(K > s || (s - K) % 2) {` ` ` `return` `0;` ` ` `}` ` ` `if` `(parseInt((s - K) / 2) & K) {` ` ` `return` `0;` ` ` `}` ` ` `// Calculate set bits in K` ` ` `let setBits = __builtin_popcount(K);` ` ` `// Calculate pairs` ` ` `let pairsCount = Math.pow(2, setBits);` ` ` `// If s = k, subtract 2 from result` ` ` `if` `(s == K)` ` ` `pairsCount -= 2;` ` ` `return` `pairsCount;` `}` `function` `__builtin_popcount(n)` `{` ` ` `/* Function to get no of set` ` ` `bits in binary representation` ` ` `of positive integer n */` ` ` `let count = 0;` ` ` `while` `(n > 0)` ` ` `{` ` ` `count += n & 1;` ` ` `n >>= 1;` ` ` `}` ` ` `return` `count;` `}` `// Driver code` ` ` `let s = 9, K = 5;` ` ` `document.write(countPairs(s, K));` `</script>` |

**Output:**

4

**Time Complexity:** O(log(K))