Given an integer n, the task is to find the number of possible values of 0 ? x ? n which satisfy n XOR x = n – x.
Examples:
Input: n = 5
Output: 4
Following values of x satisfy the equation
5 XOR 0 = 5 – 0 = 5
5 XOR 1 = 5 – 1 = 4
5 XOR 4 = 5 – 4 = 1
5 XOR 5 = 5 – 5 = 0Input: n = 2
Output: 2
Naive approach: The easy approach is to check for all values from 0 to n (both inclusive) and finding whether they satisfy the equation. The below code implements this approach:
Below is the implementation of the above approach:
C++
// C++ implementation of the approach #include<bits/stdc++.h> using namespace std; // Function to return the count of // valid values of x static int countX( int n) { int count = 0; for ( int i = 0; i <= n; i++) { // If n - x = n XOR x if (n - i == (n ^ i)) count++; } // Return the required count; return count; } // Driver code int main() { int n = 5; int answer = countX(n); cout << answer; } // This code is contributed by // Shivi_Aggarwal |
Java
// Java implementation of the approach public class GFG { // Function to return the count of // valid values of x static int countX( int n) { int count = 0 ; for ( int i = 0 ; i <= n; i++) { // If n - x = n XOR x if (n - i == (n ^ i)) count++; } // Return the required count; return count; } // Driver code public static void main(String args[]) { int n = 5 ; int answer = countX(n); System.out.println(answer); } } |
Python3
# Python3 implementation of the approach import math as mt # Function to return the count of # valid values of x def countX(n): count = 0 for i in range (n + 1 ): if n - i = = (n ^ i): count + = 1 return count # Driver Code if __name__ = = '__main__' : n = 5 answer = countX(n) print (answer) # This code is contributed by # Mohit kumar 29 |
C#
// C# implementation of the above approach using System; class GFG { // Function to return the count of // valid values of x static int countX( int n) { int count = 0; for ( int i = 0; i <= n; i++) { // If n - x = n XOR x if (n - i == (n ^ i)) count++; } // Return the required count; return count; } // Driver code public static void Main() { int n = 5; int answer = countX(n); Console.WriteLine(answer); } } // This code is contributed by Ryuga |
PHP
<?php // PHP implementation of the approach // Function to return the count of // valid values of x function countX( $n ) { $count = 0; for ( $i = 0; $i <= $n ; $i ++) { // If n - x = n XOR x if ( $n - $i == ( $n ^ $i )) $count ++; } // Return the required count; return $count ; } // Driver code $n = 5; $answer = countX( $n ); echo ( $answer ); // This code is Contributed // by Mukul Singh. ?> |
Javascript
<script> // Javascript implementation of the approach // Function to return the count of // valid values of x function countX(n) { let count = 0; for (let i = 0; i <= n; i++) { // If n - x = n XOR x if (n - i == (n ^ i)) count++; } // Return the required count; return count; } // Driver code let n = 5; let answer = countX(n); document.write(answer); </script> |
4
Time complexity: O(N)
Auxiliary Space: O(1)
Efficient Approach: Convert n to its binary representation. Now, for every 1 in the binary string whether we subtract 1 or 0 from it, it will be equivalent to XOR of 1 with 0 or 1 i.e.
(1 – 1) = (1 XOR 1) = 0
(1 – 0) = (1 XOR 0) = 1
But 0 doesn’t satisfy this condition. So, we only need to consider all the ones in the binary representation of n. Now, for every 1 there are two possibilities, either 0 or 1. Thus if we have m number of 1’s in n then our solution would be 2m.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach #include<bits/stdc++.h> using namespace std; // Function to return the count of // valid values of x int countX( int n) { // Convert n into binary String string binary = bitset<8>(n).to_string(); // To store the count of 1s int count = 0; for ( int i = 0; i < binary.length(); i++) { // If current bit is 1 if (binary.at(i) == '1' ) count++; } // Calculating answer int answer = ( int ) pow (2, count); return answer; } // Driver code int main() { int n = 5; int answer = countX(n); cout << (answer); } // This code is contributed by Rajput-Ji |
Java
// Java implementation of the approach public class GFG { // Function to return the count of // valid values of x static int countX( int n) { // Convert n into binary String String binary = Integer.toBinaryString(n); // To store the count of 1s int count = 0 ; for ( int i = 0 ; i < binary.length(); i++) { // If current bit is 1 if (binary.charAt(i) == '1' ) count++; } // Calculating answer int answer = ( int )Math.pow( 2 , count); return answer; } // Driver code public static void main(String args[]) { int n = 5 ; int answer = countX(n); System.out.println(answer); } } |
Python3
# Python3 implementation of the approach # Function to return the count of # valid values of x def countX(n): # Convert n into binary String binary = "{0:b}" . format (n) # To store the count of 1s count = 0 for i in range ( len (binary)): # If current bit is 1 if (binary[i] = = '1' ): count + = 1 # Calculating answer answer = int ( pow ( 2 , count)) return answer # Driver code if __name__ = = "__main__" : n = 5 answer = countX(n) print (answer) # This code is contributed by ita_c |
C#
// C# implementation of the approach using System; class GFG { // Function to return the count of // valid values of x static int countX( int n) { // Convert n into binary String string binary = Convert.ToString(n, 2); // To store the count of 1s int count = 0; for ( int i = 0; i < binary.Length; i++) { // If current bit is 1 if (binary[i] == '1' ) count++; } // Calculating answer int answer = ( int )Math.Pow(2, count); return answer; } // Driver code public static void Main() { int n = 5; int answer = countX(n); Console.WriteLine(answer); } } // This code is contributed // by Akanksha Rai |
Javascript
<script> // Javascript implementation of the approach // Function to return the count of // valid values of x function countX(n) { // Convert n into binary String let binary = (n >>> 0).toString(2); // To store the count of 1s let count = 0; for (let i = 0; i < binary.length; i++) { // If current bit is 1 if (binary[i] == '1' ) count++; } // Calculating answer let answer = Math.floor(Math.pow(2, count)); return answer; } // Driver code let n = 5; let answer = countX(n); document.write(answer); // This code is contributed by avanitrachhadiya2155 </script> |
4
Time complexity:
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!