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 xint 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 codeint main(){ int n = 3; cout << numberOfSolutions(n); return 0;} |
Java
// Java implementation of above approachimport java.util.*;import java.lang.*;class GFG{// Function to find the number of// solutions of n = n xor xstatic 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 codepublic 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 xdef 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 codeif __name__ == "__main__": n = 3 print(numberOfSolutions(n))# This code is contributed # by ChitraNayal |
C#
// C# implementation of above approachusing System;class GFG{// Function to find the number of// solutions of n = n xor xstatic 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 codepublic 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 xfunction 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> |
Output:
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 xint 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 codeint main(){ int n = 3; cout << numberOfSolutions(n); return 0;} |
Java
// Java implementation of above approachimport java.io.*;class GFG {// Function to find the number of// solutions of n = n xor xstatic 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 everythingfrom 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 approachusing System;class GFG{// Function to find the number of// solutions of n = n xor xstatic 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 codepublic 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> |
Output:
4
Time complexity: O(log n)
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!
