Given an integer 
. Find the number of solutions of 
which satisfies the equation:
a = b + (a^b)
Examples:
Input: a = 4 Output: 2 The only values of b are 0 and 4 itself. Input: a = 3 Output: 4
A naive solution is to iterate from 0 to and count the number of values that satisfies the given equation. We need to traverse only till since any value greater than will give the XOR value > , hence cannot satisfy the equation.
Below is the implementation of the above approach:
C++
// C++ program to find the number of values// of b such that a = b + (a^b)#include <bits/stdc++.h>using namespace std;// function to return the number of solutionsint countSolutions(int a){ int count = 0; // check for every possible value for (int i = 0; i <= a; i++) { if (a == (i + (a ^ i))) count++; } return count;}// Driver Codeint main(){ int a = 3; cout << countSolutions(a);} |
Java
// Java program to find the number of values// of b such that a = b + (a^b)import java.io.*;class GFG {// function to return the number of solutions static int countSolutions(int a){ int count = 0; // check for every possible value for (int i = 0; i <= a; i++) { if (a == (i + (a ^ i))) count++; } return count;}// Driver Code public static void main (String[] args) { int a = 3; System.out.println( countSolutions(a)); }}// This code is contributed by inder_verma |
Python3
# Python 3 program to find # the number of values of b# such that a = b + (a^b)# function to return the # number of solutionsdef countSolutions(a): count = 0 # check for every possible value for i in range(a + 1): if (a == (i + (a ^ i))): count += 1 return count# Driver Codeif __name__ == "__main__": a = 3 print(countSolutions(a))# This code is contributed# by ChitraNayal |
C#
// C# program to find the number of // values of b such that a = b + (a^b)using System;class GFG {// function to return the// number of solutionsstatic int countSolutions(int a){ int count = 0; // check for every possible value for (int i = 0; i <= a; i++) { if (a == (i + (a ^ i))) count++; } return count;}// Driver Codepublic static void Main () { int a = 3; Console.WriteLine(countSolutions(a));}}// This code is contributed by inder_verma |
PHP
<?php// PHP program to find the number of // values of b such that a = b + (a^b)// function to return the // number of solutionsfunction countSolutions($a){ $count = 0; // check for every possible value for ($i = 0; $i <= $a; $i++) { if ($a == ($i + ($a ^ $i))) $count++; } return $count;}// Driver Code$a = 3;echo countSolutions($a);// This code is contributed // by inder_verma?> |
Javascript
<script>// Javascript program to find the number of values// of b such that a = b + (a^b)// function to return the number of solutionsfunction countSolutions(a){ let count = 0; // check for every possible value for (let i = 0; i <= a; i++) { if (a == (i + (a ^ i))) count++; } return count;}// Driver Codelet a = 3;document.write(countSolutions(a));</script> |
Output:
4
Time Complexity: O(a), since there runs a loop for a times.
Auxiliary Space: O(1), since no extra space has been taken.
An Efficient Approach is to observe a pattern of answers when we write the possible solutions for different values of . Only the set bits are used to determine the number of possible answers. The answer to the problem will always be 2^(number of set bits) which can be determined by observation.
Below is the implementation of the above approach:
C++
// C++ program to find the number of values// of b such that a = b + (a^b)#include <bits/stdc++.h>using namespace std;// function to return the number of solutionsint countSolutions(int a){ int count = __builtin_popcount(a); count = pow(2, count); return count;}// Driver Codeint main(){ int a = 3; cout << countSolutions(a);} |
Java
// Java program to find the number of values// of b such that a = b + (a^b)import java.io.*;class GFG{ // function to return the number of solutions static int countSolutions(int a) { int count = Integer.bitCount(a); count =(int) Math.pow(2, count); return count; } // Driver Code public static void main (String[] args) { int a = 3; System.out.println(countSolutions(a)); }}// This code is contributed by Raj |
Python3
# Python3 program to find the number # of values of b such that a = b + (a^b) # function to return the number # of solutions def countSolutions(a): count = bin(a).count('1') return 2 ** count # Driver Code if __name__ == "__main__": a = 3 print(countSolutions(a)) # This code is contributed by# Rituraj Jain |
C#
// C# program to find the number of // values of b such that a = b + (a^b)class GFG{// function to return the number // of solutionsstatic int countSolutions(int a){ int count = bitCount(a); count =(int) System.Math.Pow(2, count); return count;}static int bitCount(int n){ int count = 0; while (n != 0) { count++; n &= (n - 1); } return count;}// Driver Codepublic static void Main() { int a = 3; System.Console.WriteLine(countSolutions(a));}}// This code is contributed by mits |
PHP
<?php// PHP program to find the number of // values of b such that a = b + (a^b)// function to return the number // of solutionsfunction countSolutions($a){ $count = bitCount($a); $count = (int)pow(2, $count); return $count;}function bitCount($n){ $count = 0; while ($n != 0) { $count++; $n &= ($n - 1); } return $count;}// Driver Code$a = 3;echo (countSolutions($a));// This code is contributed by ajit?> |
Javascript
<script>// Javascript program to find the number// of values of b such that a = b + (a^b)function bitCount(n){ let count = 0; while (n != 0) { count++; n &= (n - 1); } return count;}// Function to return the number of solutionsfunction countSolutions(a){ let count = bitCount(a); count = Math.pow(2, count); return count;}// Driver Codelet a = 3;document.write(countSolutions(a));// This code is contributed by subhammahato348</script> |
Output:
4
Time Complexity: O(log N) since inbuilt pow function has been used which takes logarithmic time.
Auxiliary Space: O(1), since no extra space has been taken.
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!
