Find the triplet from given Bitwise XOR and Bitwise AND values of all its pairs
Given six positive integers representing the Bitwise XOR and Bitwise AND of all possible pairs of a triplet (a, b, c), the task is to find the triplet.
Examples:
Input: aXORb = 30, aANDb = 0, aXORc = 10, aANDc = 20, aXORb = 20, aANDb = 10
Output: a = 10, b = 20, c= 30
Explanation:
If a = 10, b = 20, c= 30
a ^ b = 30, a & b = 0
a ^ c = 10, a & c = 20
a ^ b = 20, a & b = 10
Therefore, the required output is (a, b, c) = (10, 20, 30).Input: aXORb = 3, aANDb = 0, aXORc = 2, aANDc = 1, aXORb = 1, aANDb = 2
Output: a = 1, b = 2, c = 3
Approach: The idea is to find the sum of every possible pairs of triplet using their Bitwise XOR and Bitwise AND values based on the following observations:
a + b = a ^ b + 2 * (a & b)
Follow the steps below to solve the problem:
- Find the sum of every possible pair of triplets i.e, (a + b, b + c, c + a) using the above formula.
- The value of a can be calculated as ((a + b) + (a + c) – (b + c)) / 2.
- The value of b can be calculated as ((a + b) – a).
- The value of c can be calculated as ((b + c) – b).
- Finally, print the value of the triplet (a, b, c).
Below is the implementation of the above approach:
C++
// C++ program to implement // the above approach #include <bits/stdc++.h> using namespace std; // Function to find the triplet with given // Bitwise XOR and Bitwise AND values of all // possible pairs of the triplet void findNumbers( int aXORb, int aANDb, int aXORc, int aANDc, int bXORc, int bANDc) { // Stores values of // a triplet int a, b, c; // Stores a + b int aSUMb; // Stores a + c int aSUMc; // Stores b + c int bSUMc; // Calculate aSUMb aSUMb = aXORb + aANDb * 2; // Calculate aSUMc aSUMc = aXORc + aANDc * 2; // Calculate bSUMc bSUMc = bXORc + bANDc * 2; // Calculate a a = (aSUMb - bSUMc + aSUMc) / 2; // Calculate b b = aSUMb - a; // Calculate c c = aSUMc - a; // Print a cout << "a = " << a; // Print b cout << ", b = " << b; // Print c cout << ", c = " << c; } // Driver Code int main() { int aXORb = 30, aANDb = 0, aXORc = 20, aANDc = 10, bXORc = 10, bANDc = 20; findNumbers(aXORb, aANDb, aXORc, aANDc, bXORc, bANDc); } |
Java
// Java program to implement // the above approach class GFG{ // Function to find the triplet with given // Bitwise XOR and Bitwise AND values of all // possible pairs of the triplet static void findNumbers( int aXORb, int aANDb, int aXORc, int aANDc, int bXORc, int bANDc) { // Stores values of // a triplet int a, b, c; // Stores a + b int aSUMb; // Stores a + c int aSUMc; // Stores b + c int bSUMc; // Calculate aSUMb aSUMb = aXORb + aANDb * 2 ; // Calculate aSUMc aSUMc = aXORc + aANDc * 2 ; // Calculate bSUMc bSUMc = bXORc + bANDc * 2 ; // Calculate a a = (aSUMb - bSUMc + aSUMc) / 2 ; // Calculate b b = aSUMb - a; // Calculate c c = aSUMc - a; // Print a System.out.print( "a = " + a); // Print b System.out.print( ", b = " + b); // Print c System.out.print( ", c = " + c); } // Driver Code public static void main(String[] args) { int aXORb = 30 , aANDb = 0 , aXORc = 20 , aANDc = 10 , bXORc = 10 , bANDc = 20 ; findNumbers(aXORb, aANDb, aXORc, aANDc, bXORc, bANDc); } } // This code is contributed by 29AjayKumar |
Python3
# Python program to implement # the above approach # Function to find the triplet with given # Bitwise XOR and Bitwise AND values of all # possible pairs of the triplet def findNumbers(aXORb, aANDb, aXORc, aANDc, bXORc, bANDc): # Stores values of # a triplet a, b, c = 0 , 0 , 0 ; # Stores a + b aSUMb = 0 ; # Stores a + c aSUMc = 0 ; # Stores b + c bSUMc = 0 ; # Calculate aSUMb aSUMb = aXORb + aANDb * 2 ; # Calculate aSUMc aSUMc = aXORc + aANDc * 2 ; # Calculate bSUMc bSUMc = bXORc + bANDc * 2 ; # Calculate a a = (aSUMb - bSUMc + aSUMc) / / 2 ; # Calculate b b = aSUMb - a; # Calculate c c = aSUMc - a; # Pra print ( "a = " , a, end = ""); # Prb print ( ", b = " , b, end = ""); # Prc print ( ", c = " , c, end = ""); # Driver Code if __name__ = = '__main__' : aXORb = 30 ; aANDb = 0 ; aXORc = 20 ; aANDc = 10 ; bXORc = 10 ; bANDc = 20 ; findNumbers(aXORb, aANDb, aXORc, aANDc, bXORc, bANDc); # This code contributed by shikhasingrajput |
C#
// C# code for above approach using System; public class GFG { // Function to find the triplet with given // Bitwise XOR and Bitwise AND values of all // possible pairs of the triplet static void findNumbers( int aXORb, int aANDb, int aXORc, int aANDc, int bXORc, int bANDc) { // Stores values of // a triplet int a, b, c; // Stores a + b int aSUMb; // Stores a + c int aSUMc; // Stores b + c int bSUMc; // Calculate aSUMb aSUMb = aXORb + aANDb * 2; // Calculate aSUMc aSUMc = aXORc + aANDc * 2; // Calculate bSUMc bSUMc = bXORc + bANDc * 2; // Calculate a a = (aSUMb - bSUMc + aSUMc) / 2; // Calculate b b = aSUMb - a; // Calculate c c = aSUMc - a; // Print a System.Console.Write( "a = " + a); // Print b System.Console.Write( ", b = " + b); // Print c System.Console.Write( ", c = " + c); } // Driver code static public void Main () { int aXORb = 30, aANDb = 0, aXORc = 20, aANDc = 10, bXORc = 10, bANDc = 20; findNumbers(aXORb, aANDb, aXORc, aANDc, bXORc, bANDc); } } // This code is contributed by offbeat. |
Javascript
<script> // JavaScript program to implement // the above approach // Function to find the triplet with given // Bitwise XOR and Bitwise AND values of all // possible pairs of the triplet function findNumbers(aXORb, aANDb, aXORc, aANDc, bXORc, bANDc) { // Stores values of // a triplet let a, b, c; // Stores a + b let aSUMb; // Stores a + c let aSUMc; // Stores b + c let bSUMc; // Calculate aSUMb aSUMb = aXORb + aANDb * 2; // Calculate aSUMc aSUMc = aXORc + aANDc * 2; // Calculate bSUMc bSUMc = bXORc + bANDc * 2; // Calculate a a = Math.floor((aSUMb - bSUMc + aSUMc) / 2); // Calculate b b = aSUMb - a; // Calculate c c = aSUMc - a; // Print a document.write( "a = " + a); // Print b document.write( ", b = " + b); // Print c document.write( ", c = " + c); } // Driver Code let aXORb = 30, aANDb = 0, aXORc = 20, aANDc = 10, bXORc = 10, bANDc = 20; findNumbers(aXORb, aANDb, aXORc, aANDc, bXORc, bANDc); // This code is contributed by Surbhi Tyagi. </script> |
a = 10, b = 20, c = 30
Time Complexity: O(1)
Auxiliary Space: O(1)
Contact Us