Given an integer N, the task is to find the number of distinct values possible for the bit-wise XOR of X and Y where 1 ≤ X, Y ≤ N.
Examples:
Input: N = 1
Output: 1
Explanation: The possible xor values are 1⊕1=0 which has 1 unique value.Input: N = 2
Output: 2
Explanation: The possible xor values are 1⊕1 = 0, 1⊕2 = 1, 2⊕2 = 0 which has 2 unique values.
Approach: For the values of N equals 1 and 2, the answer is simple. For the remaining cases, consider N≥3. Consider p as the highest power for which 2^p ≤ N. Suppose 2^p < N, then all the numbers from 0 to 2^{p+1} -1 can be obtained. This can be achieved in the following way:
For example,
let N = 12, then x = 3.
Number 12 (1100 in binary ) can be formed by (2^3(1000), 4(0100)).
By the property of xor, num⊕1 is either num +1 or num -1.
So if 1 < num ≤ 2^p < N, 1 ≤ num⊕1 ≤ N.
Hence these pairs of numbers will always be valid.
Now, what happens if 2^p = N? All of the above cases hold true except for the case of num = 2^p. This cannot be obtained from any xor pair (X, Y) where (1 ≤ X, Y ≤ 2^p). Since the only number with bit p set is 2^p, we must keep i = 2^p. Then for X ⊕ Y=2*p, Keep Y = 0, which cannot be done since Y ≥ 1. Hence, in this case, except 2^p, xor pair for any number from 0 to 2^{p + 1} -1 can be obtained. Follow the steps below to solve the problem:
- Initialize the variable ans as 1.
- If N equals 2 then print 2 and return.
- Traverse in a while loop till ans is less than N and multiply ans by 2.
- If ans equals N then multiply ans by 2 and reduce it’s value by 1.
- After performing the above steps, print the value of ans as the answer.
Below is the implementation of the above approach.
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;int MOD = 1e9 + 7;// Function to find the possible valuesvoid find(long long N){ long long ans = 1; // Special case if (N == 2) { cout << 2 << endl; return; } while (ans < N) { ans *= 2; } if (ans == N) { ans *= 2; ans--; } cout << ans % MOD;}// Driver Codeint main(){ long long N = 7; find(N); return 0;} |
Java
// Java program for the above approachimport java.io.*;import java.lang.*;import java.util.*;class GFG { // Function to find the possible values static void find(long N) { long MOD = 1000000007; long ans = 1; // Special case if (N == 2) { System.out.println("2"); return; } while (ans < N) { ans *= 2; } if (ans == N) { ans *= 2; ans--; } long temp = ans % MOD; System.out.print(temp); } // Driver Code public static void main (String[] args) { long N = 7; find(N); }}// This code is contributed by hrithikgarg03188. |
Python
# Python program for the above approach# Function to find the possible valuesdef find(N): MOD = 1000000007 ans = 1 # Special case if (N == 2): print(2) return; while ans < N: ans *= 2 if (ans == N): ans *= 2 ans -= 1 print(ans % MOD)if __name__ == "__main__": N = 7 find(N) # This code is contributed by hrithikgarg03188. |
C#
// C# program to implement// the above approachusing System;class GFG{// Function to find the possible values static void find(long N) { long MOD = 1000000007; long ans = 1; // Special case if (N == 2) { Console.WriteLine("2"); return; } while (ans < N) { ans *= 2; } if (ans == N) { ans *= 2; ans--; } long temp = ans % MOD; Console.Write(temp); }// Driver Codepublic static void Main(){ long N = 7; find(N);}}// This code is contributed by Samim Hossain Mondal. |
Javascript
<script> // JavaScript code for the above approach let MOD = 1e9 + 7; // Function to find the possible values function find(N) { let ans = 1; // Special case if (N == 2) { document.write(2 + '<br>') return; } while (ans < N) { ans *= 2; } if (ans == N) { ans *= 2; ans--; } document.write(ans % MOD); } // Driver Code let N = 7; find(N); // This code is contributed by Potta Lokesh </script> |
8
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!
