Minimum Increment or Bitwise OR operations to make two integers equal
Given two integers X and Y (X < Y), we can perform the following operations any number of times:
- Increment X by 1, X = X + 1
- Increment Y by 1, Y = Y + 1
- Change X to X | Y, X = X | Y
The task is to determine the minimum number of operations required to make X = Y.
Input: X = 1, Y = 3
Output: 1
Explanation: It takes only one operation to make X = Y,
- Apply type 3 operation (X = X | Y), so X = 1 | 3 = 3 and Y = 3.
Input: X = 5, Y = 8
Output: 3
Explanation: It takes three operations to make X = Y,
- Perform type 1 operation (X = X + 1), so X = 6, Y = 8
- Perform type 1 operation (X = X + 1), so X = 7, Y = 8
- Perform type 1 operation (X = X + 1), so X = 8, Y = 8
Approach: To solve the problem, follow the below idea:
It can be observed that its optimal to apply type 3 operation at most once as if we apply X = X | Y, the value of X will become greater than or equal to Y. So, if it becomes equal to Y then we don’t need to apply any operation otherwise if it becomes greater than Y, then we need to apply only type 2 operations.
Now, we know that the max number of operations needed are (Y – X). Let’s say we apply some type 1 operations and some type 2 operations before applying type 3 operation, so the new value of X becomes X1 and the new value of Y becomes Y1 before performing the type 3 operation. So, now the total operations needed will be: F = (X1 – X) + (Y1 – Y) + ((X1 | Y1) – Y1) + 1, which can be simplified as F = X1 + (X1 | Y1) – (X + Y – 1). Now, we need minimize F which is same as minimizing X1 + (X1 | Y1), since (X + Y – 1) is constant.
We can iterate X1 from X to Y and for a fixed X1, we need to minimize the value of X1 | Y1, so we can construct Y1 bit by bit as follows:
- If ith bit of X1 = 0 and Y = 0, so ith bit of Y1 will be 0.
- If ith bit of X1 = 0 and Y = 1, so ith bit of Y1 will be 1.
- If ith bit of X1 = 1 and Y = 0, so ith bit of Y1 will be 1 and break.
- If ith bit of X1 = 1 and Y = 1, so ith bit of Y1 will be 1.
Step-by-step algorithm:
- Initialize minimum operations = Y – X.
- Iterate X1 from X to Y, and for every X1,
- Construct Y1 bit by bit.
- Calculate total number of operations as currentOperations.
- Update min operations if currentOperations < min operations.
- Return min operations as the answer.
Below is the implementation of the algorithm:
C++
#include <bits/stdc++.h> using namespace std; int getMinOperations( int X, int Y) { int minOperations = Y - X; for ( int X1 = X; X1 <= Y; X1 ++) { int currentOperations = 0; // Operations needed to convert X to X1 currentOperations += (X1 - X); int Y1 = 0; for ( int j = 30; j >= 0; j --) { // Find jth bit of X1 int bitX1 = (X1 >> j) & 1; // Find jth bit of Y int bitY = (Y >> j) & 1; if ((bitX1 == 0 && bitY == 1) || (bitX1 == 1 && bitY == 1)) { Y1 |= (1 << j); } else if (bitX1 == 1 && bitY == 0) { Y1 |= (1 << j); break ; } } // Operations needed to convert Y to Y1 currentOperations += (Y1 - Y); // One operation of type 3 currentOperations += 1; // Operations needed to convert Y1 to (X1 | Y1) currentOperations += ((X1 | Y1) - Y1); minOperations = min(minOperations, currentOperations); } return minOperations; } int main() { cout << getMinOperations(1, 3) << "\n" ; cout << getMinOperations(5, 8) << "\n" ; return 0; } |
Java
public class Main { public static int getMinOperations( int X, int Y) { int minOperations = Y - X; for ( int X1 = X; X1 <= Y; X1++) { int currentOperations = 0 ; // Operations needed to convert X to X1 currentOperations += (X1 - X); int Y1 = 0 ; for ( int j = 30 ; j >= 0 ; j--) { // Find jth bit of X1 int bitX1 = (X1 >> j) & 1 ; // Find jth bit of Y int bitY = (Y >> j) & 1 ; if ((bitX1 == 0 && bitY == 1 ) || (bitX1 == 1 && bitY == 1 )) { Y1 |= ( 1 << j); } else if (bitX1 == 1 && bitY == 0 ) { Y1 |= ( 1 << j); break ; } } // Operations needed to convert Y to Y1 currentOperations += (Y1 - Y); // One operation of type 3 currentOperations += 1 ; // Operations needed to convert Y1 to (X1 | Y1) currentOperations += ((X1 | Y1) - Y1); minOperations = Math.min(minOperations, currentOperations); } return minOperations; } public static void main(String[] args) { System.out.println(getMinOperations( 1 , 3 )); System.out.println(getMinOperations( 5 , 8 )); } } // This code is contributed by akshitaguprzj3 |
C#
using System; class GFG { static int GetMinOperations( int X, int Y) { int minOperations = Y - X; for ( int X1 = X; X1 <= Y; X1++) { int currentOperations = 0; // Operations needed to convert X to X1 currentOperations += (X1 - X); int Y1 = 0; for ( int j = 30; j >= 0; j--) { // Find jth bit of X1 int bitX1 = (X1 >> j) & 1; // Find jth bit of Y int bitY = (Y >> j) & 1; if ((bitX1 == 0 && bitY == 1) || (bitX1 == 1 && bitY == 1)) { Y1 |= (1 << j); } else if (bitX1 == 1 && bitY == 0) { Y1 |= (1 << j); break ; } } // Operations needed to convert Y to Y1 currentOperations += (Y1 - Y); // One operation of type 3 currentOperations += 1; // Operations needed to convert Y1 to (X1 | Y1) currentOperations += ((X1 | Y1) - Y1); minOperations = Math.Min(minOperations, currentOperations); } return minOperations; } static void Main() { Console.WriteLine(GetMinOperations(1, 3)); Console.WriteLine(GetMinOperations(5, 8)); } } |
Javascript
// JavaScript Implementation function getMinOperations(X, Y) { let minOperations = Y - X; for (let X1 = X; X1 <= Y; X1++) { let currentOperations = 0; // Operations needed to convert X to X1 currentOperations += (X1 - X); let Y1 = 0; for (let j = 30; j >= 0; j--) { // Find jth bit of X1 let bitX1 = (X1 >> j) & 1; // Find jth bit of Y let bitY = (Y >> j) & 1; if ((bitX1 === 0 && bitY === 1) || (bitX1 === 1 && bitY === 1)) { Y1 |= (1 << j); } else if (bitX1 === 1 && bitY === 0) { Y1 |= (1 << j); break ; } } // Operations needed to convert Y to Y1 currentOperations += (Y1 - Y); // One operation of type 3 currentOperations += 1; // Operations needed to convert Y1 to (X1 | Y1) currentOperations += ((X1 | Y1) - Y1); minOperations = Math.min(minOperations, currentOperations); } return minOperations; } console.log(getMinOperations(1, 3)); console.log(getMinOperations(5, 8)); // This code is contributed by Tapesh(tapeshdu420) |
Python3
def get_min_operations(X, Y): min_operations = Y - X for X1 in range (X, Y + 1 ): current_operations = 0 # Operations needed to convert X to X1 current_operations + = (X1 - X) Y1 = 0 for j in range ( 30 , - 1 , - 1 ): # Find jth bit of X1 bit_X1 = (X1 >> j) & 1 # Find jth bit of Y bit_Y = (Y >> j) & 1 if (bit_X1 = = 0 and bit_Y = = 1 ) or (bit_X1 = = 1 and bit_Y = = 1 ): Y1 | = ( 1 << j) elif bit_X1 = = 1 and bit_Y = = 0 : Y1 | = ( 1 << j) break # Operations needed to convert Y to Y1 current_operations + = (Y1 - Y) # One operation of type 3 current_operations + = 1 # Operations needed to convert Y1 to (X1 | Y1) current_operations + = ((X1 | Y1) - Y1) min_operations = min (min_operations, current_operations) return min_operations if __name__ = = "__main__" : print (get_min_operations( 1 , 3 )) print (get_min_operations( 5 , 8 )) |
1 3
Time Complexity: O(X log Y), where X and Y are the two input numbers.
Auxiliary Space: O(1)