Given two integers X and Y, the task is to find the minimum number of operations required to make X equal to Y by performing the given operations such that:
- X = X + 1
- Y = Y + 1
- X = X | Y
Examples:
Input: X = 4, Y = 5
Output: 1
Explanation: Applying 1st operation one time X = X + 1 => 4 + 1 => 5 (Thus, both numbers become equal).Input: X = 2, Y = 5
Output: 2
Explanation: Apply second operation on Y and then 3rd operation (bitwise OR with Y).
So first Y will become 6 and then 2|6 = 6 in second step.
Approach: The problem can be solved using bitwise techniques as per the following observation:
- Operation 3 should be applied only once, as (X | Y) is always greater than or equal to max(X, Y)
- After operation 3, because of the reason mentioned the next operation (if needed) will always be incrementing Y by 1 to have minimum number of steps.
- If operation 3 is not used at any time, answer = Y – X.
Now to generalize the above idea in terms of formula and cost for each step :-
let’s say the initial value is given = (X, Y) -> and we would be calculating cost at each step as well.
- Then Cost1 => 0, (initial cost)
- The increased value = (newX, newY) (assume newX and newY as new values if they are increased some number of times)
Then difference of increased value with original(initial) value) Cost2 = [(newX – Y) + (newY – Y)]- Applying operation 3(only once as discussed above) on previous term X and Y will be [(newX | newY), newY]
So cost for this will be Cost3 = Cost2 + 1\- After applying operation 2 on previous terms to make them equal, they will be [(newX | newY), (newX | newY)]
Then Cost4 = Cost3 + (newX | newY – newY)(i.e, this would turn out to be cost for making newY equal to newX term)- Thus, overall cost after reducing terms would be = Cost2 + Cost3 + Cost4 = newX + (newX | newY) + [1 – X – Y].
- Assuming the last term to be constant our final equation would turn out to be => newX + (newX | newY)
[Reduced Term]To minimize the overall cost, we have to minimize the reduced term. For doing so, iterate over all possible values of newX and greedily find the value of newY. To construct newY, iterate from MSB(highest bit) to LSB(lowest bit).
Follow the steps mentioned below to minimize the value of reduced term mentioned in the observation:
- If the ith bit is set in newX, then:
- If the bit is not set in Y, set bit in newY and break;
- Else, set the bit in newY as well.
- if the ith bit is not set in newX, then-
- newY for that bit would be equal to Y for that bit.
- In the end, compute the minimum for each iteration, and return the final minimum answer.
Below is the implementation of the above approach:
C++
// C++ code to find the minimum// number of steps to make// first number equal to second#include <bits/stdc++.h>using namespace std;// Function to do required operationint solve(int x, int y){ // Initializing answer variable int answer = 0; // Can say that our default // answer would be y - x answer = y - x; // Iterating from x to y // for each newX for (int newX = x; newX <= y; newX++) { // Initialize newY to be 0 int newY = 0; // Now, greedily try // to minimize (newX | newY) // while ensuring that newY >= y for (int i = 20; i >= 0; i--) { // Now, check for above // discussed two cases // If i'th bit is set in newX if ((newX & (1 << i))) { // If i'th bit is not set // in newY if (!(y & (1 << i))) { // This makes newY >= y, // along with minimizing //(newX | newY) newY += (1 << i); break; } else { // (newX | newY) will remain // same set bit in newY newY += (1 << i); } } // If i'th bit is not set // in newX else { if (y & (1 << i)) { // Set bit in newY newY += (1 << i); } else { // Continue or // just add 0 newY += 0; } } } // Computing minimum of each // iteration with generated formula answer = min(answer, newX + (newX | newY) + (1 - x - y)); } // Printing final answer return answer;}// Driver codeint main(){ // Taking input int X = 2, Y = 5; // Function call cout << solve(X, Y); return 0;} |
Java
// Java code to find the minimum// number of steps to make// first number equal to secondimport java.io.*;class GFG { // Function to do required operation static int solve(int x, int y) { // Initializing answer variable int answer = 0; // Can say that our default // answer would be y - x answer = y - x; // Iterating from x to y // for each newX for (int newX = x; newX <= y; newX++) { // Initialize newY to be 0 int newY = 0; // Now, greedily try // to minimize (newX | newY) // while ensuring that newY >= y for (int i = 20; i >= 0; i--) { // Now, check for above // discussed two cases // If i'th bit is set in newX if ((newX & (1 << i)) != 0) { // If i'th bit is not set // in newY if ((y & (1 << i)) == 0) { // This makes newY >= y, // along with minimizing //(newX | newY) newY += (1 << i); break; } else { // (newX | newY) will remain // same set bit in newY newY += (1 << i); } } // If i'th bit is not set // in newX else { if ((y & (1 << i)) != 0) { // Set bit in newY newY += (1 << i); } else { // Continue or // just add 0 newY += 0; } } } // Computing minimum of each // iteration with generated formula answer = Math.min(answer, newX + (newX | newY) + (1 - x - y)); } // Printing final answer return answer; } // Driver code public static void main (String[] args) { // Taking input int X = 2, Y = 5; // Function call System.out.print(solve(X, Y)); }}// This code is contributed by hrithikgarg03188. |
Python3
# Python code for the above approach# Function to do required operationdef solve(x, y): # Initializing answer variable answer = 0 # Can say that our default # answer would be y - x answer = y - x; # Iterating from x to y # for each newX for newX in range(x,y+1): # Initialize newY to be 0 newY = 0 # Now, greedily try # to minimize (newX | newY) # while ensuring that newY >= y for i in range(20,-1,-1): # Now, check for above # discussed two cases # If i'th bit is set in newX if ((newX & (1 << i))): # If i'th bit is not set # in newY if (~(y & (1 << i))): # This makes newY >= y, # along with minimizing #(newX | newY) newY += (1 << i) break else: # (newX | newY) will remain # same set bit in newY newY += (1 << i) # If i'th bit is not set # in newX else: if (y & (1 << i)): # Set bit in newY newY += (1 << i) else: # Continue or # just add 0 newY += 0 # Computing minimum of each # iteration with generated formula answer = min(answer,newX + (newX | newY) + (1 - x - y)) # Printing final answer return answer# Driver code# Taking inputX,Y = 2,5# function callprint(solve(X, Y))# This code is contributed by shinjanpatra |
C#
// C# code to find the minimum// number of steps to make// first number equal to secondusing System;class GFG { // Function to do required operation static int solve(int x, int y) { // Initializing answer variable int answer = 0; // Can say that our default // answer would be y - x answer = y - x; // Iterating from x to y // for each newX for (int newX = x; newX <= y; newX++) { // Initialize newY to be 0 int newY = 0; // Now, greedily try // to minimize (newX | newY) // while ensuring that newY >= y for (int i = 20; i >= 0; i--) { // Now, check for above // discussed two cases // If i'th bit is set in newX if ((newX & (1 << i)) != 0) { // If i'th bit is not set // in newY if ((y & (1 << i)) == 0) { // This makes newY >= y, // along with minimizing //(newX | newY) newY += (1 << i); break; } else { // (newX | newY) will remain // same set bit in newY newY += (1 << i); } } // If i'th bit is not set // in newX else { if ((y & (1 << i)) != 0) { // Set bit in newY newY += (1 << i); } else { // Continue or // just add 0 newY += 0; } } } // Computing minimum of each // iteration with generated formula answer = Math.Min(answer, newX + (newX | newY) + (1 - x - y)); } // Printing final answer return answer; } // Driver code public static void Main() { // Taking input int X = 2, Y = 5; // Function call Console.Write(solve(X, Y)); }}// This code is contributed by Samim Hossain Mondal. |
Javascript
<script> // JavaScript code for the above approach// Function to do required operationfunction solve(x, y){ // Initializing answer variable let answer = 0; // Can say that our default // answer would be y - x answer = y - x; // Iterating from x to y // for each newX for (let newX = x; newX <= y; newX++) { // Initialize newY to be 0 let newY = 0; // Now, greedily try // to minimize (newX | newY) // while ensuring that newY >= y for (let i = 20; i >= 0; i--) { // Now, check for above // discussed two cases // If i'th bit is set in newX if ((newX & (1 << i))) { // If i'th bit is not set // in newY if (!(y & (1 << i))) { // This makes newY >= y, // along with minimizing //(newX | newY) newY += (1 << i); break; } else { // (newX | newY) will remain // same set bit in newY newY += (1 << i); } } // If i'th bit is not set // in newX else { if (y & (1 << i)) { // Set bit in newY newY += (1 << i); } else { // Continue or // just add 0 newY += 0; } } } // Computing minimum of each // iteration with generated formula answer = Math.min(answer, newX + (newX | newY) + (1 - x - y)); } // Printing final answer return answer;}// Driver code // Taking input let X = 2, Y = 5; // Function call document.write(solve(X, Y)); // This code is contributed by Potta Lokesh </script> |
Output
2
Time Complexity: O(Y * logY)
Auxiliary Space: O(1)
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!
