Given an integer N count the number of values of X such that X⊕N > N, where ⊕ denotes bitwise XOR operation
Examples:
Input: N = 10
Output: 5
Explanation: The five possible value satisfying the above condition are:
1⊕10 = 11, 4⊕10 = 14, 5⊕10 = 15, 6⊕10 = 12, 7⊕10 = 13Input: N = 8
Output: 7
Explanation: The seven possible value satisfying the above condition are:
1⊕8 = 9, 2⊕8 = 10, 3⊕8 = 11, 4⊕8 = 12, 5⊕8 = 13, 6⊕8 = 14, 7⊕8 = 15
Naive Approach: The simple approach to this problem is to iterate from 1 to N and increment the count if X XOR N >N for 0 < X < N. Finally, return the count of the number of values.
Time Complexity: O(N)
Auxiliary Space: O(1)
Efficient Approach: The most efficient approach is to find the number nearest to the next power of 2 which has all its bits set and finally subtract it from the original number. Given below is the mathematical observation of the solution:
If number N can be written by using k bits then number X must use k-1 bits at most because:-
- If a number X has a same bits as number N Xoring both the number will result in a number less than N which wont satisfy our condition X xor N > N.
- If a number X is greater than number N then Xoring both the number will always result X is greater than N which wont satisfy our inequality.
So the problem reduces to find the count of the number that lies in the given range [x , 2k – 1]. We are taking 2k – 1 because this is the maximum number that can be form when all its n bits are set.- The require number equals 2k – 1 -N .
Follow the steps below to solve the problem:
- Find the nearest next power of 2.
- Subtract 1 from the nearest power of 2 so that the given number has all its bit set
- Finally, subtract from the original number and return it
Below is the implementation of the above approach:
C++
// C++ program for find the count of// number of value of X such that N XOR X >N#include <bits/stdc++.h>using namespace std;// Function for calculating the total// possible value satisfy the condition// X⊕N > N and 0 < X < Nvoid maximumXor(long long N){ long long num = N; long long int count; count = 0; while (N > 0) { // Count the total number of bits count++; N = N / 2; } long long next_power = ((long long)1 << count); // Finding the next power of 2 // of the given number long long result = next_power - 1; // Finding the number nearest to // the nextpower of 2 which has all // its bits set cout << result - num;}// Driver Codeint main(){ int N = 10; maximumXor(N); return 0;} |
Java
// Java program for find the count of// number of value of X such that N XOR X >Nimport java.util.*;public class GFG { // Function for calculating the total // possible value satisfy the condition // X⊕N > N and 0 < X < N static void maximumXor(long N) { long num = N; long count = 0; count = 0; while (N > 0) { // Count the total number of bits count++; N = N / 2; } long next_power = ((long)1 << count); // Finding the next power of 2 // of the given number long result = next_power - 1; // Finding the number nearest to // the nextpower of 2 which has all // its bits set System.out.print(result - num); } // Driver Code public static void main(String args[]) { int N = 10; maximumXor(N); }}// This code is contributed by Samim Hossain Mondal. |
Python3
# python3 program for find the count of# number of value of X such that N XOR X >N# Function for calculating the total# possible value satisfy the condition# X⊕N > N and 0 < X < Ndef maximumXor(N): num = N count = 0 while (N > 0): # Count the total number of bits count += 1 N = N // 2 next_power = (1 << count) # Finding the next power of 2 # of the given number result = next_power - 1 # Finding the number nearest to # the nextpower of 2 which has all # its bits set print(result - num)# Driver Codeif __name__ == "__main__": N = 10 maximumXor(N)# This code is contributed by rakeshsahni |
C#
// C# program for find the count of// number of value of X such that N XOR X >Nusing System;public class GFG{ // Function for calculating the total // possible value satisfy the condition // X⊕N > N and 0 < X < N static void maximumXor(long N) { long num = N; long count = 0; count = 0; while (N > 0) { // Count the total number of bits count++; N = N / 2; } long next_power = (1 << (int)count); // Finding the next power of 2 // of the given number long result = next_power - 1; // Finding the number nearest to // the nextpower of 2 which has all // its bits set Console.Write(result - num); } // Driver Code public static void Main(String []args) { int N = 10; maximumXor(N); }}// This code is contributed by 29AjayKumar |
Javascript
<script> // JavaScript code for the above approach // Function for calculating the total // possible value satisfy the condition // X⊕N > N and 0 < X < N function maximumXor(N) { let num = N; let count; count = 0; while (N > 0) { // Count the total number of bits count++; N = Math.floor(N / 2); } let next_power = (1 << count); // Finding the next power of 2 // of the given number let result = next_power - 1; // Finding the number nearest to // the nextpower of 2 which has all // its bits set document.write(result - num); } // Driver Code let N = 10; maximumXor(N); // This code is contributed by Potta Lokesh </script> |
5
Time Complexity: O(log(N))
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!