Minimize operations to make X equal to Y by replacing X with its bitwise XOR with N
Given two integers X and Y, and an integer K, the task is to find the minimum number of operations to make X equal to Y by choosing a number N in range (1 ≤ N < K) and applying the XOR operation as X = X XOR N. If it is not possible, return -1.
Examples:
Input: X = 7, Y = 1, K = 5
Output: 2
Explanation: Since in binary, X = 7 -> 111, Y = 1 -> 001,
and given that K = 5, N can be in range [1, 4].
Now there is need to change 2 bits in X to make it equal to Y.
Therefore possible values of N can be 6 (110), 4 (100), 2 (010)
- We cannot choose 6 as it is not in range [1, 4]
- We will choose 4, making X as X XOR 4 = 111 XOR 100 = 011
- Now again we will choose 2, making X as 011 XOR 010 = 001, which is same as Y.
Thus, 2 operations are needed to convert X to Y.
Input: X = 3, Y = 4, K = 10
Output: 1
Approach: To solve the problem follow the below observations:
Let V be the XOR of X and Y. Now, we want to get V by performing XOR of as few elements as possible, no more than N,
Decrease the value of K by 1 so that we don’t select N = K for performing XOR.
We observe the following three cases:
- if V = 0: Then we need zero operations because V=0 means X⊕Y=0 which implies X is already equal to Y.
- if V < K: Then we need only 1 operation because V < K implies it is always possible to find a number N less than equal to K
which on XOR with X will give Y.
- If log2(V) = log2(K): In 1st operation we can change the most significant bit only,
and in 2nd operation we can change all bits less than most significant one.
Hence 2 operations.Else it is not possible to make X equal to Y by doing XOR. This happens in the case where the largest bit of V is greater than the largest bit of K, which means we cannot create this largest bit by any means. Hence we print -1.
Follow the given steps to solve the problem:
- Decrease K by 1 to avoid selecting N = K for XOR.
- Store the XOR of X and Y in a variable (say V).
- Now, find the minimum number of operations required based on the above conditions.
Below is the implementation of the above approach.
C++
// C++ code to implement the approach #include <bits/stdc++.h> using namespace std; // Function to find the minimum number of steps int equalByXOR( int X, int Y, int K) { // Decreasing K by 1 to avoid // selecting N == K for XORing K--; // Ctr variable to count the number of // operations required int ctr = 0; // V be the XOR of X and Y int V = X ^ Y; // Cases as discussed above in approach // 3 cases if possible if (V == 0) { ctr = 0; } else if (V <= K) { ctr = 1; } else if (K != 0 && __lg(V) == __lg(K)) { ctr = 2; } else { // If not possible ctr = -1; } // Return the minimum number of operations return ctr; } // Driver code int main() { int X = 7, Y = 1, K = 5; // Function call cout << equalByXOR(X, Y, K); return 0; } |
Java
// Java code to implement the approach import java.util.*; class GFG{ // Function to find the minimum number of steps static int equalByXOR( int X, int Y, int K) { // Decreasing K by 1 to avoid // selecting N == K for XORing K--; // Ctr variable to count the number of // operations required int ctr = 0 ; // V be the XOR of X and Y int V = X ^ Y; // Cases as discussed above in approach // 3 cases if possible if (V == 0 ) { ctr = 0 ; } else if (V <= K) { ctr = 1 ; } else if (K != 0 && Integer.highestOneBit(V) == Integer.highestOneBit(K)) { ctr = 2 ; } else { // If not possible ctr = - 1 ; } // Return the minimum number of operations return ctr; } // Driver code public static void main(String[] args) { int X = 7 , Y = 1 , K = 5 ; // Function call System.out.print(equalByXOR(X, Y, K)); } } // This code contributed by shikhasingrajput |
Python3
# Python code to implement the approach import math # Function to find the minimum number of steps def equalByXOR(X, Y, K): # Decreasing K by 1 to avoid # selecting N == K for XORing K - = 1 # Ctr variable to count the number of # operations required ctr = 0 # V be the XOR of X and Y V = X ^ Y # Cases as discussed above in approach # 3 cases if possible if V = = 0 : ctr = 0 elif V < = K: ctr = 1 elif K ! = 0 and int (math.log(V)) = = int (math.log(K)): ctr = 2 else : # If not possible ctr = - 1 # Return the minimum number of operations return ctr # Driver code if __name__ = = "__main__" : X = 7 Y = 1 K = 5 # Function call print (equalByXOR(X, Y, K)) # This code is contributed by Rohit Pradhan |
C#
// C# code to implement the approach using System; class Program { // Function to find the minimum number of steps public static int equalByXOR( int X, int Y, int K) { // Decreasing K by 1 to avoid selecting N == K for XORing K -= 1; // Ctr variable to count the number of operations required int ctr = 0; // V be the XOR of X and Y int V = X ^ Y; // Cases as discussed above in approach 3 cases if possible if (V == 0) ctr = 0; else if (V <= K) ctr = 1; else if (K != 0 && ( int )Math.Log(V) == ( int )Math.Log(K)) ctr = 2; else // If not possible ctr = -1; // Return the minimum number of operations return ctr; } // Driver code public static void Main( string [] args) { int X = 7, Y = 1, K = 5; // Function call Console.WriteLine(equalByXOR(X, Y, K)); } } // This code is contributed by Tapesh(tapeshdua420) |
Javascript
<script> // JavaScript program for above approach: // Function to find the minimum number of steps function equalByXOR(X, Y, K) { // Decreasing K by 1 to avoid // selecting N == K for XORing K--; // Ctr variable to count the number of // operations required let ctr = 0; // V be the XOR of X and Y let V = X ^ Y; // Cases as discussed above in approach // 3 cases if possible if (V == 0) { ctr = 0; } else if (V <= K) { ctr = 1; } else if (K != 0 && Math.floor(Math.log(V)) == Math.floor(Math.log(K))) { ctr = 2; } else { // If not possible ctr = -1; } // Return the minimum number of operations return ctr; } // Driver Code let X = 7, Y = 1, K = 5; // Function call document.write(equalByXOR(X, Y, K)); // This code is contributed by code_hunt. </script> |
2
Time Complexity: O(1)
Auxiliary Space: O(1)