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 = 5 Output : 4 The ordered pairs are (2, 7), (3, 6), (6, 3), (7, 2) Input : S = 2, K = 2 Output : 0 There are no such ordered pair.
Approach: For any two integers a and b
Sum S = a + b can be written as S = (a
b) + (a & b)*2
Where a
This is because 
is non-carrying binary addition. Thus we can write a & b = (S-K)/2 where S=(a + b) and K = (a 
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 ai = bi, so we have one possibility: ai = bi = (ai & bi).
- If, (a b) = 1 then we must have (ai & bi) = 0 (otherwise the output is 0), and we have two choices: either (ai = 1 and bi = 0) or (ai = 0 and bi = 1).
Where ai is the i-th bit in a and bi 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 Kint 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 codeint 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 codeif __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 Codepublic 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 Kfunction 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)), Auxiliary Space: O (1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
