Given a integer ‘x’, find the number of values of ‘a’ satisfying the following conditions:
- 0 <= a <= x
- a XOR x = a + x
Examples :
Input : 5 Output : 2 Explanation: For x = 5, following 2 values of 'a' satisfy the conditions: 5 XOR 0 = 5+0 5 XOR 2 = 5+2 Input : 10 Output : 4 Explanation: For x = 10, following 4 values of 'a' satisfy the conditions: 10 XOR 0 = 10+0 10 XOR 1 = 10+1 10 XOR 4 = 10+4 10 XOR 5 = 10+5
Naive Approach:
A Simple approach is to check for all values of ‘a’ between 0 and ‘x’ (both inclusive) and calculate its XOR with x and check if the condition 2 satisfies.
Below is the implementation of the above idea:
C++
// C++ program to find count of values whose XOR// with x is equal to the sum of value and x// and values are smaller than equal to x#include <bits/stdc++.h>using namespace std;int FindValues(int x){ // Initialize result int count = 0; // Traversing through all values between // 0 and x both inclusive and counting // numbers that satisfy given property for (int i = 0; i <= x; i++) if ((x + i) == (x ^ i)) count++; return count;}// Driver codeint main(){ int x = 10; // Function call cout << FindValues(x); return 0;} |
Java
// Java program to find count of values whose XOR// with x is equal to the sum of value and x// and values are smaller than equal to xclass Fib { static int FindValues(int x) { // Initialize result int count = 0; // Traversing through all values between // 0 and x both inclusive and counting // numbers that satisfy given property for (int i = 0; i <= x; i++) if ((x + i) == (x ^ i)) count++; return count; } // Driver code public static void main(String[] args) { int x = 10; // Function call System.out.println(FindValues(x)); }} |
Python3
# Python3 program to find count of# values whose XOR with x is equal# to the sum of value and x and# values are smaller than equal to xdef FindValues(x): # Initialize result count = 0 # Traversing through all values # between 0 and x both inclusive # and counting numbers that # satisfy given property for i in range(0, x): if ((x + i) == (x ^ i)): count = count + 1 return count# Driver codex = 10# Function callprint(FindValues(x))# This code is contributed# by Shivi_Aggarwal |
C#
// C# program to find count of values whose XOR// with x is equal to the sum of value and x// and values are smaller than equal to xusing System;class Fib{ static int FindValues(int x) { // Initialize result int count = 0; // Traversing through all values between // 0 and x both inclusive and counting // numbers that satisfy given property for (int i = 0; i <= x; i++) if ((x + i) == (x ^ i)) count++; return count; } // Driver code public static void Main() { int x = 10; // Function call Console.Write(FindValues(x)); }}// This code is contributed by Nitin Mittal. |
PHP
<?php// PHP program to find count// of values whose XOR with x// is equal to the sum of value// and x and values are smaller// than equal to x// function return the // value of countfunction FindValues($x){ // Initialize result $count = 0; // Traversing through all values between // 0 and x both inclusive and counting // numbers that satisfy given property for ($i = 0; $i <= $x; $i++) if (($x + $i) == ($x ^ $i)) $count++; return $count;} // Driver code $x = 10; // Function call echo FindValues($x); // This code is contributed by anuj_67.?> |
Javascript
<script> // Javascript program to find count of values whose XOR // with x is equal to the sum of value and x // and values are smaller than equal to x function FindValues(x) { // Initialize result let count = 0; // Traversing through all values between // 0 and x both inclusive and counting // numbers that satisfy given property for (let i = 0; i <= x; i++) if ((x + i) == (x ^ i)) count++; return count; } let x = 10; // Function call document.write(FindValues(x)); </script> |
Output
4
Time complexity: O(x).
Auxiliary Space: O(1)
Efficient Approach:
XOR simulates binary addition without the carry over to the next digit. For the zero digits of ‘a’ we can either add a 1 or 0 without getting a carry which implies xor = + whereas if a digit in ‘a’ is 1 then the matching digit in x is forced to be 0 in order to avoid carry. For each 0 in ‘a’ in the matching digit in x can either being a 1 or 0 with a total combination count of 2^(num of zero). Hence, we just need to count the number of 0’s in binary representation of the number and answer will by 2^(number of zeroes).
Below is the implementation of the above idea:
C++
// C++ program to count numbers whose bitwise// XOR and sum with x are equal#include <bits/stdc++.h>using namespace std;// Function to find total 0 bit in a numberlong CountZeroBit(long x){ unsigned int count = 0; while (x) { if (!(x & 1LL)) count++; x >>= 1LL; } return count;}// Function to find Count of non-negative numbers// less than or equal to x, whose bitwise XOR and// SUM with x are equal.long CountXORandSumEqual(long x){ // count number of zero bit in x long count = CountZeroBit(x); // power of 2 to count return (1LL << count);}// Driver codeint main(){ long x = 10; // Function call cout << CountXORandSumEqual(x); return 0;} |
Java
// Java program to count// numbers whose bitwise// XOR and sum with x// are equalimport java.io.*;class GFG { // Function to find total // 0 bit in a number static long CountZeroBit(long x) { long count = 0; while (x > 0) { if ((x & 1L) == 0) count++; x >>= 1L; } return count; } // Function to find Count // of non-negative numbers // less than or equal to x, // whose bitwise XOR and // SUM with x are equal. static long CountXORandSumEqual(long x) { // count number of // zero bit in x long count = CountZeroBit(x); // power of 2 to count return (1L << count); } // Driver code public static void main(String[] args) { long x = 10; // Function call System.out.println(CountXORandSumEqual(x)); }}// The code is contributed by ajit |
Python3
# Python3 program to count numbers whose bitwise# XOR and sum with x are equal# Function to find total 0 bit in a numberdef CountZeroBit(x): count = 0 while (x): if ((x & 1) == 0): count += 1 x >>= 1 return count# Function to find Count of non-negative numbers# less than or equal to x, whose bitwise XOR and# SUM with x are equal.def CountXORandSumEqual(x): # count number of zero bit in x count = CountZeroBit(x) # power of 2 to count return (1 << count)# Driver codeif __name__ == '__main__': x = 10 # Function call print(CountXORandSumEqual(x))# This code is contributed by 29AjayKumar |
C#
// C# program to count// numbers whose bitwise// XOR and sum with x// are equalusing System;class GFG { // Function to find total // 0 bit in a number static int CountZeroBit(int x) { int count = 0; while (x > 0) { if ((x & 1) == 0) count++; x >>= 1; } return count; } // Function to find Count // of non-negative numbers // less than or equal to x, // whose bitwise XOR and // SUM with x are equal. static int CountXORandSumEqual(int x) { // count number of // zero bit in x int count = CountZeroBit(x); // power of 2 to count return (1 << count); } // Driver code static public void Main() { int x = 10; // Function call Console.WriteLine(CountXORandSumEqual(x)); }}// The code is contributed by ajit |
PHP
<?php// PHP program to count numbers whose bitwise// XOR and sum with x are equal// Function to find total 0 bit in a numberfunction CountZeroBit($x){ $count = 0; while ($x) { if (!($x & 1)) $count++; $x >>= 1; } return $count;}// Function to find Count of// non-negative numbers less// than or equal to x, whose// bitwise XOR and SUM with// x are equal.function CountXORandSumEqual($x){ // count number of zero bit in x $count = CountZeroBit($x); // power of 2 to count return (1 << $count);} // Driver code $x = 10; // Function call echo CountXORandSumEqual($x);// This code is contributed by m_kit?> |
Javascript
<script>// Javascript program to count// numbers whose bitwise// XOR and sum with x// are equal// Function to find total// 0 bit in a numberfunction CountZeroBit(x){ let count = 0; while (x > 0) { if ((x & 1) == 0) count++; x >>= 1; } return count;}// Function to find Count// of non-negative numbers// less than or equal to x,// whose bitwise XOR and// SUM with x are equal.function CountXORandSumEqual(x){ // count number of // zero bit in x let count = CountZeroBit(x); // power of 2 to count return (1 << count);}// Driver codelet x = 10; // Function calldocument.write(CountXORandSumEqual(x));// This code is contributed by suresh07</script> |
Output
4
Time complexity: O(Log x)
Auxiliary Space: O(1)
This article is contributed by DANISH KALEEM. If you like neveropen and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks.
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
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!
