Equal Sum and XOR of three Numbers
Given an integer N. The task is to count the numbers of pairs of integers A and B such that A + B + N = A ^ B ^ N and A and B are less than N.
Examples:
Input: N = 2
Output: 3
Explanation:-
For N = 2
2 XOR 0 XOR 0 = 2+0+0
2 XOR 0 XOR 1 = 2+0+1
2 XOR 0 XOR 2 != 2+0+2
2 XOR 1 XOR 0 = 2+1+0
2 XOR 1 XOR 1 != 2+1+1
2 XOR 1 XOR 2 != 2+1+2
2 XOR 2 XOR 0 != 2+2+0
2 XOR 2 XOR 1 != 2+2+1
2 XOR 2 XOR 2 != 2+2+2
So (0, 0), (0, 1) and (1, 0) are the required pairs. So the output is 3.
Input: N = 4
Output: 9
Approach :
To make the sum of three numbers equal to the xor of three number with one of the number given we can do following:-
- Represent the fixed number in binary form.
- Traverse the binary expansion of the fixed number.
- If you find a 1 there is only one condition i.e. you take the other two number’s binary bits as 0 and 0.
- If you find a 0 there will be three conditions i.e. either you can have binary bits as (0, 0), (1, 0)
or (0, 1).
- The following triplets of bits will never go for a carry so they are valid.
- So the answer will be 3^(number of zeros in binary representation).
Below is the implementation of the above approach:
C++
// C++ implementation of the above approach #include <bits/stdc++.h> using namespace std; // Defining ull to unsigned long long int typedef unsigned long long int ull; // Function to calculate power of 3 ull calculate( int bit_cnt) { ull res = 1; while (bit_cnt--) { res = res * 3; } return res; } // Function to return the count of the // unset bit ( zeros ) int unset_bit_count(ull n) { int count = 0; while (n) { // Check the bit is 0 or not if ((n & 1) == 0) count++; // Right shifting ( dividing by 2 ) n = n >> 1; } return count; } // Driver Code int main() { ull n; n = 2; int count = unset_bit_count(n); ull ans = calculate(count); cout << ans << endl; return 0; } |
Java
// Java implementation of the approach import java.util.*; class GFG { // Function to calculate power of 3 static long calculate( int bit_cnt) { long res = 1 ; while (bit_cnt-- > 0 ) { res = res * 3 ; } return res; } // Function to return the count of the // unset bit ( zeros ) static int unset_bit_count( long n) { int count = 0 ; while (n > 0 ) { // Check the bit is 0 or not if ((n & 1 ) == 0 ) count++; // Right shifting ( dividing by 2 ) n = n >> 1 ; } return count; } // Driver Code public static void main(String[] args) { long n; n = 2 ; int count = unset_bit_count(n); long ans = calculate(count); System.out.println(ans); } } // This code is contributed by PrinciRaj1992 |
Python3
# Python3 implementation of the approach # Function to calculate power of 3 def calculate(bit_cnt): res = 1 ; while (bit_cnt > 0 ): bit_cnt - = 1 ; res = res * 3 ; return res; # Function to return the count of the # unset bit ( zeros ) def unset_bit_count(n): count = 0 ; while (n > 0 ): # Check the bit is 0 or not if ((n & 1 ) = = 0 ): count + = 1 ; # Right shifting ( dividing by 2 ) n = n >> 1 ; return count; # Driver Code if __name__ = = '__main__' : n = 2 ; count = unset_bit_count(n); ans = calculate(count); print (ans); # This code contributed by Rajput-Ji |
C#
// C# implementation of the approach using System; class GFG { // Function to calculate power of 3 static long calculate( int bit_cnt) { long res = 1; while (bit_cnt-- > 0) { res = res * 3; } return res; } // Function to return the count of the // unset bit (zeros) static int unset_bit_count( long n) { int count = 0; while (n > 0) { // Check the bit is 0 or not if ((n & 1) == 0) count++; // Right shifting ( dividing by 2 ) n = n >> 1; } return count; } // Driver Code public static void Main(String[] args) { long n; n = 2; int count = unset_bit_count(n); long ans = calculate(count); Console.WriteLine(ans); } } // This code is contributed by 29AjayKumar |
Javascript
<script> // Javascript implementation of // the above approach // Function to calculate power of 3 function calculate(bit_cnt) { let res = 1; while (bit_cnt--) { res = res * 3; } return res; } // Function to return the count of the // unset bit ( zeros ) function unset_bit_count(n) { let count = 0; while (n) { // Check the bit is 0 or not if ((n & 1) == 0) count++; // Right shifting ( dividing by 2 ) n = n >> 1; } return count; } // Driver Code let n; n = 2; let count = unset_bit_count(n); let ans = calculate(count); document.write(ans); </script> |
Output:
3
Time Complexity: O(Number of unset_bits).
Auxiliary Space: O(1).
Contact Us