XOR counts of 0s and 1s in binary representation
Given a number, the task is to find XOR of count of 0s and count of 1s in binary representation of a given number.
Examples:
Input : 5 Output : 3 Binary representation : 101 Count of 0s = 1, Count of 1s = 2 1 XOR 2 = 3. Input : 7 Output : 3 Binary representation : 111 Count of 0s = 0 Count of 1s = 3 0 XOR 3 = 3.
The idea is simple, we traverse through all bits of a number, count 0s and 1s and finally return XOR of two counts.
C++
// C++ program to find XOR of counts 0s and 1s in // binary representation of n. #include<iostream> using namespace std; // Returns XOR of counts 0s and 1s in // binary representation of n. int countXOR( int n) { int count0 = 0, count1 = 0; while (n) { //calculating count of zeros and ones (n % 2 == 0) ? count0++ :count1++; n /= 2; } return (count0 ^ count1); } // Driver Program int main() { int n = 31; cout << countXOR (n); return 0; } |
Java
// Java program to find XOR of counts 0s // and 1s in binary representation of n. class GFG { // Returns XOR of counts 0s and 1s // in binary representation of n. static int countXOR( int n) { int count0 = 0 , count1 = 0 ; while (n != 0 ) { //calculating count of zeros and ones if (n % 2 == 0 ) count0++ ; else count1++; n /= 2 ; } return (count0 ^ count1); } // Driver Program public static void main(String[] args) { int n = 31 ; System.out.println(countXOR (n)); } } // This code is contributed by prerna saini |
Python3
# Python3 program to find XOR of counts 0s # and 1s in binary representation of n. # Returns XOR of counts 0s and 1s # in binary representation of n. def countXOR(n): count0, count1 = 0 , 0 while (n ! = 0 ): # calculating count of zeros and ones if (n % 2 = = 0 ): count0 + = 1 else : count1 + = 1 n / / = 2 return (count0 ^ count1) # Driver Code n = 31 print (countXOR(n)) # This code is contributed by Anant Agarwal. |
C#
// C# program to find XOR of counts 0s // and 1s in binary representation of n. using System; class GFG { // Returns XOR of counts 0s and 1s // in binary representation of n. static int countXOR( int n) { int count0 = 0, count1 = 0; while (n != 0) { // calculating count of zeros // and ones if (n % 2 == 0) count0++ ; else count1++; n /= 2; } return (count0 ^ count1); } // Driver Program public static void Main() { int n = 31; Console.WriteLine(countXOR (n)); } } // This code is contributed by Anant Agarwal. |
PHP
<?PHP // PHP program to find XOR of // counts 0s and 1s in binary // representation of n. // Returns XOR of counts 0s and 1s // in binary representation of n. function countXOR( $n ) { $count0 = 0; $count1 = 0; while ( $n ) { // calculating count of // zeros and ones ( $n % 2 == 0) ? $count0 ++ : $count1 ++; $n = intval ( $n / 2); } return ( $count0 ^ $count1 ); } // Driver Code $n = 31; echo countXOR ( $n ); // This code is contributed // by ChitraNayal ?> |
Javascript
<script> // Javascript program to find XOR of counts 0s // and 1s in binary representation of n. // Returns XOR of counts 0s and 1s // in binary representation of n. function countXOR(n) { let count0 = 0, count1 = 0; while (n != 0) { //calculating count of zeros and ones if (n % 2 == 0) count0++ ; else count1++; n = Math.floor(n/2); } return (count0 ^ count1); } // Driver Program let n = 31; document.write(countXOR (n)); // This code is contributed by avanitrachhadiya2155 </script> |
Output:
5
Time Complexity: O(log(N))
Auxiliary Space: O(1)
One observation is, for a number of the form 2^x – 1, the output is always x. We can directly produce answer for this case by first checking n+1 is a power of two or not.
Contact Us