Given a integer ‘x’, find the number of values of ‘a’ satisfying the following conditions:
- a XOR x > x
- 0 < a < x
Examples :
Input : x = 10
Output : 5
Explanation: For x = 10, following 5 values
of 'a' satisfy the conditions:
1 XOR 10 = 11
4 XOR 10 = 14
5 XOR 10 = 15
6 XOR 10 = 12
7 XOR 10 = 13
Input : x = 2
Output : 1
Explanation: For x=2, we have just one value
1 XOR 2 = 3.
Naive Approach
A Simple approach is to check for all values of ‘a’ between 0 and ‘x’ and calculate its XOR with x and check if the condition 1 satisfies.
C++
// C++ program to find count of values// whose XOR with x is greater than x// and values are smaller than x#include<bits/stdc++.h>using namespace std;int countValues(int x){ int count = 0; for (int i=1; i < x; i++) if ((i ^ x) > x) count++; return count;}// Driver codeint main(){ int x = 10; cout << countValues(x); return 0;} |
Java
// Java program to find count of values// whose XOR with x is greater than x// and values are smaller than xpublic class XOR{ static int countValues(int x) { int count = 0; for (int i=1; i < x; i++) if ((i ^ x) > x) count++; return count; } public static void main (String[] args) { int x = 10; System.out.println(countValues(x)); }}// This code is contributed by Saket Kumar |
Python3
# Python3 program to find # count of values whose# XOR with x is greater# than x and values are # smaller than xdef countValues(x): count = 0 for i in range(1 ,x): if ((i ^ x) > x): count += 1 return count# Driver codex = 10print(countValues(x))# This code is contributed # by Smitha |
C#
// C# program to find count of values// whose XOR with x is greater than x// and values are smaller than xusing System;class GFG{ static int countValues(int x) { int count = 0; for (int i = 1; i < x; i++) if ((i ^ x) > x) count++; return count; } public static void Main () { int x = 10; Console.Write(countValues(x)); }}// This code is contributed by nitin mittal. |
PHP
<?php// PHP program to find count of values// whose XOR with x is greater than x// and values are smaller than xfunction countValues($x){ $count = 0; for ($i = 1; $i < $x; $i++) if (($i ^ $x) > $x) $count++; return $count;} // Driver code $x = 10; echo countValues($x);// This code is contributed by anuj_67.?> |
Javascript
<script>// Javascript program to find count of values// whose XOR with x is greater than x// and values are smaller than xfunction countValues(x){ let count = 0; for (let i=1; i < x; i++) if ((i ^ x) > x) count++; return count;}// Driver code let x = 10; document.write(countValues(x));</script> |
Output :
5
The time complexity of the above approach is O(x).
Auxiliary Space: O(1)
Efficient Approach
The efficient solution lies in the binary representation of the number. We consider all 0’s in binary representation. For every 0 at the i-th position, we can have 2i numbers smaller than or equal to x with greater XOR.
C++
// C++ program to find count of values// whose XOR with x is greater than x// and values are smaller than x#include<bits/stdc++.h>using namespace std;int countValues(int x){ // Initialize result int count = 0, n = 1; // Traversing through all bits of x while (x != 0) { // If current last bit of x is set // then increment count by n. Here // n is a power of 2 corresponding // to position of bit if (x%2 == 0) count += n; // Simultaneously calculate the 2^n n *= 2; // Replace x with x/2; x /= 2; } return count;}// Driver codeint main(){ int x = 10; cout << countValues(x); return 0;} |
Java
// Java program to find count of values// whose XOR with x is greater than x// and values are smaller than xclass GFG{ static int countValues(int x) { // Initialize result int count = 0, n = 1; // Traversing through all bits of x while (x != 0) { // If current last bit of x is set // then increment count by n. Here // n is a power of 2 corresponding // to position of bit if (x % 2 == 0) count += n; // Simultaneously calculate the 2^n n *= 2; // Replace x with x/2; x /= 2; } return count; } // Driver code public static void main (String[] args) { int x = 10; System.out.println(countValues(x)); } }// This code is contributed by Saket Kumar |
Python3
# Python3 program to find count# of values whose XOR with# x is greater than x and # values are smaller than xdef countValues(x): # Initialize result count = 0; n = 1; # Traversing through # all bits of x while (x > 0): # If current last bit # of x is set then # increment count by # n. Here n is a power # of 2 corresponding # to position of bit if (x % 2 == 0): count += n; # Simultaneously # calculate the 2^n n *= 2; # Replace x with x/2; x /= 2; x = int(x); return count;# Driver codex = 10;print(countValues(x));# This code is contributed# by mits |
C#
// C# program to find count of values// whose XOR with x is greater than x// and values are smaller than xusing System;class GFG{ static int countValues(int x) { // Initialize result int count = 0, n = 1; // Traversing through all bits of x while (x != 0) { // If current last bit of x is set // then increment count by n. Here // n is a power of 2 corresponding // to position of bit if (x % 2 == 0) count += n; // Simultaneously calculate the 2^n n *= 2; // Replace x with x/2; x /= 2; } return count; } // Driver code public static void Main () { int x = 10; Console.Write(countValues(x)); } }// This code is contributed by nitin mittal |
PHP
<?php// PHP program to find count// of values whose XOR with// x is greater than x and // values are smaller than xfunction countValues($x){ // Initialize result $count = 0; $n = 1; // Traversing through // all bits of x while ($x != 0) { // If current last bit // of x is set then // increment count by // n. Here n is a power // of 2 corresponding // to position of bit if ($x % 2 == 0) $count += $n; // Simultaneously // calculate the 2^n $n *= 2; // Replace x with x/2; $x /= 2; $x = (int)$x; } return $count;}// Driver code$x = 10;echo countValues($x);// This code is contributed// by Smitha?> |
Javascript
<script>// Javascript program to find count of // values whose XOR with x is greater // than x and values are smaller than x function countValues(x){ // Initialize result var count = 0, n = 1; // Traversing through all bits of x while (x != 0) { // If current last bit of x is set // then increment count by n. Here // n is a power of 2 corresponding // to position of bit if (x % 2 == 0) count += n; // Simultaneously calculate the 2^n n *= 2; // Replace x with x/2; x = parseInt(x / 2); } return count;}// Driver codevar x = 10;document.write(countValues(x));// This code is contributed by Princi Singh </script> |
Output :
5
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!
