Number of solutions of n = x + n ⊕ x
Given a number n, we have to find the number of possible values of X such that n = x + n ? x. Here ? represents XOR
Examples:
Input : n = 3 Output : 4 The possible values of x are 0, 1, 2, and 3. Input : n = 2 Output : 2 The possible values of x are 0 and 2.
Brute force approach: We can see that x is always equal to or less than n, so we can iterate over the range [0, n] and count the number of values that satisfy the required condition. The time complexity of this approach is O(n).
C++
// C++ implementation of above approach #include <bits/stdc++.h> using namespace std; // Function to find the number of // solutions of n = n xor x int numberOfSolutions( int n) { // Counter to store the number // of solutions found int c = 0; for ( int x = 0; x <= n; ++x) if (n == x + n ^ x) ++c; return c; } // Driver code int main() { int n = 3; cout << numberOfSolutions(n); return 0; } |
Java
// Java implementation of above approach import java.util.*; import java.lang.*; class GFG { // Function to find the number of // solutions of n = n xor x static int numberOfSolutions( int n) { // Counter to store the number // of solutions found int c = 0 ; for ( int x = 0 ; x <= n; ++x) if (n == x + (n ^ x)) ++c; return c; } // Driver code public static void main(String args[]) { int n = 3 ; System.out.print(numberOfSolutions(n)); } } // This code is contributed // by Akanksha Rai(Abby_akku) |
Python3
# Python 3 implementation # of above approach # Function to find the number of # solutions of n = n xor x def numberOfSolutions(n): # Counter to store the number # of solutions found c = 0 for x in range (n + 1 ): if (n = = ( x + ( n ^ x))): c + = 1 return c # Driver code if __name__ = = "__main__" : n = 3 print (numberOfSolutions(n)) # This code is contributed # by ChitraNayal |
C#
// C# implementation of above approach using System; class GFG { // Function to find the number of // solutions of n = n xor x static int numberOfSolutions( int n) { // Counter to store the number // of solutions found int c = 0; for ( int x = 0; x <= n; ++x) if (n == x + (n ^ x)) ++c; return c; } // Driver code public static void Main() { int n = 3; Console.Write(numberOfSolutions(n)); } } // This code is contributed // by Akanksha Rai(Abby_akku) |
PHP
<?php // PHP implementation of above approach // Function to find the number of // solutions of n = n xor x function numberOfSolutions( $n ) { // Counter to store the number // of solutions found $c = 0; for ( $x = 0; $x <= $n ; ++ $x ) if ( $n == $x + $n ^ $x ) ++ $c ; return $c ; } // Driver code $n = 3; echo numberOfSolutions( $n ); // This code is contributed // by Akanksha Rai(Abby_akku) |
Javascript
<script> // Javascript implementation of above approach // Function to find the number of // solutions of n = n xor x function numberOfSolutions(n) { // Counter to store the number // of solutions found let c = 0; for (let x = 0; x <= n; ++x) if (n == x + n ^ x) ++c; return c; } let n = 3; document.write(numberOfSolutions(n)); // This code is contributed by divyesh072019. </script> |
4
Time complexity: O(n)
Auxiliary Space: O(1)
Efficient approach: We can solve this problem in a more efficient way if we consider n in its binary form. If a bit of n is set, i.e. 1, then we can deduce that there must be a corresponding set bit in either x or n ? x (but not both). If the corresponding bit is set in x, then it is not set in n ? x as 1 ? 1 = 0. Otherwise the bit is set in n ? x as 0 ? 1 = 1. Therefore for every set bit in n, we can have either a set bit or an unset bit in x. However, we cannot have a set bit in x corresponding to an unset bit in n. By this logic, the number of solutions comes out to be 2 raised to the power of the number of set bits in n. The time complexity of this approach is O(log n).
C++
// C++ implementation of above approach #include <bits/stdc++.h> using namespace std; // Function to find the number of // solutions of n = n xor x int numberOfSolutions( int n) { // Number of set bits in n int c = 0; while (n) { c += n % 2; n /= 2; } // We can also write (1 << c) return pow (2, c); } // Driver code int main() { int n = 3; cout << numberOfSolutions(n); return 0; } |
Java
// Java implementation of above approach import java.io.*; class GFG { // Function to find the number of // solutions of n = n xor x static int numberOfSolutions( int n) { // Number of set bits in n int c = 0 ; while (n> 0 ) { c += n % 2 ; n /= 2 ; } // We can also write (1 << c) return ( int )Math.pow( 2 , c); } // Driver code public static void main (String[] args) { int n = 3 ; System.out.println( numberOfSolutions(n)); } } //This code is contributed by anuj_67 |
Python3
# Python3 implementation of above approach # from math lib. import everything from math import * # Function to find the number of # solutions of n = n xor x def numberOfSolutions(n) : # Number of set bits in n c = 0 while (n) : c + = n % 2 n / / = 2 # We can also write (1 << c) return int ( pow ( 2 , c)) # Driver code if __name__ = = "__main__" : n = 3 print (numberOfSolutions(n)) # This code is contributed by ANKITRAI1 |
C#
// C# implementation of above approach using System; class GFG { // Function to find the number of // solutions of n = n xor x static int numberOfSolutions( int n) { // Number of set bits in n int c = 0; while (n > 0) { c += n % 2; n /= 2; } // We can also write (1 << c) return ( int )Math.Pow(2, c); } // Driver code public static void Main () { int n = 3; Console.WriteLine(numberOfSolutions(n)); } } // This code is contributed by anuj_67 |
PHP
<?php // PHP implementation of above approach // Function to find the number of // solutions of n = n xor x function numberOfSolutions( $n ) { // Number of set bits in n $c = 0; while ( $n ) { $c += $n % 2; $n /= 2; } // We can also write (1 << c) return pow(2, $c ); } // Driver code $n = 3; echo numberOfSolutions( $n ); // This code is contributed by jit_t ?> |
Javascript
<script> // Javascript implementation of above approach // Function to find the number of // solutions of n = n xor x function numberOfSolutions(n) { // Number of set bits in n let c = 0; while (n > 0) { c += n % 2; n = parseInt(n / 2, 10); } // We can also write (1 << c) return Math.pow(2, c); } let n = 3; document.write(numberOfSolutions(n)); </script> |
4
Time complexity: O(log n)
Auxiliary Space: O(1)
Contact Us