Given two numbers a and b, the task is to find the minimum number of operations required to make a and b equal. In each operation, we can pick a non-negative integer x and either a or b. If a is chosen, we replace a with the bitwise AND (&) of a and x. If b is chosen, we replace b with the bitwise AND of b and x. The goal is to perform the minimum number of operations to make a and b equal.
Examples:
Input: a = 5, b = 12
Output: 2
Explanation: In the first operation replace a = a&4 = 4 after that replace b = b&6 = 4. Hence both are same after applying two operations.Input: a = 100, b = 100
Output: 0
Explanation: Already the same.
Approach: To solve this problem, we can follow the following observations:
Observations:
- If a is equal to b, we don’t need to perform any operations. In this case, we return 0.
- If either a or b is zero, we can make them equal by performing the AND operation of the non-zero digit with zero. Since this requires one operation, we return 1.
- If the result of the AND operation between a and b is equal to either a or b, it means all the set bits in the result are also set in either a or b. In this case, we can make a and b equal by performing one operation. We return 1.
- If none of the above conditions are met, the differing bits between a and b cannot be eliminated in one operation. In the worst case, we must perform two operations to make them equal. Therefore, we return 2.
Below is the implementation for the above approach::
C++
// C++ code for the aboeva pproach:#include <bits/stdc++.h>using namespace std;int solve(int a, int b){ // If a and b are equal, // no operations required if (a == b) return 0; // If either a or b is zero, // perform one operation if (a == 0 || b == 0) return 1; // Calculate the bitwise // AND of a and b int x = a & b; // If x is equal to either a or b, // perform one operation if (a == x || b == x) return 1; // Otherwise, perform two operations return 2;}// Drivers codeint main(){ int a = 5, b = 12; // Function call int result = solve(a, b); cout << result << endl; return 0;} |
Java
public class Main { public static int solve(int a, int b) { // If a and b are equal, // no operations required if (a == b) return 0; // If either a or b is zero, // perform one operation if (a == 0 || b == 0) return 1; // Calculate the bitwise AND of a and b int x = a & b; // If x is equal to either a // or b, perform one operation if (a == x || b == x) return 1; // Otherwise, perform two operations return 2; } public static void main(String[] args) { int a = 5, b = 12; // Function Call int result = solve(a, b); System.out.println(result); }}// This code is contributed by Jeetu Bangari |
Python3
def solve(a, b): # If a and b are equal, # no operations required if a == b: return 0# If either a or b is zero,# perform one operation if a == 0 or b == 0: return 1# Calculate the bitwise# AND of a and b x = a & b # If x is equal to either a or b, # perform one operation if a == x or b == x: return 1# Otherwise, perform two operations return 2a = 5b = 12# Function Callresult = solve(a, b)print(result)# This code is contributed by Jeetu Bangari |
C#
using System;class GFG{ static int Solve(int a, int b) { // If a and b are equal, // no operations required if (a == b) return 0; // If either a or b is zero, // perform one operation if (a == 0 || b == 0) return 1; // Calculate the bitwise // AND of a and b int x = a & b; // If x is equal to either a or b, // perform one operation if (a == x || b == x) return 1; // Otherwise, perform two operations return 2; } // Driver code static void Main(string[] args) { int a = 5, b = 12; // Function call int result = Solve(a, b); Console.WriteLine(result); Console.ReadLine(); }} |
Javascript
function solve(a, b) {// If a and b are equal, no operations required if (a === b) return 0; // If either a or b is zero, perform one operation if (a === 0 || b === 0) return 1;// Calculate the bitwise AND of a and b let x = a & b; // If x is equal to either a or b, perform one operation if (a === x || b === x) return 1; // Otherwise, perform two operations return 2; }let a = 5;let b = 12;//Function calllet result = solve(a, b);console.log(result);// This code is contributed by Jeetu Bangari |
2
Time Complexity: O(1), as it takes constant time.
Auxiliary space: O(1), as it uses constant space.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
