|
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++
#include <bits/stdc++.h>
using namespace std;
int solve(int a, int b)
{
if (a == b)
return 0;
if (a == 0 || b == 0)
return 1;
int x = a & b;
if (a == x || b == x)
return 1;
return 2;
}
int main()
{
int a = 5, b = 12;
int result = solve(a, b);
cout << result << endl;
return 0;
}
|
Java
public class Main {
public static int solve(int a, int b)
{
if (a == b)
return 0;
if (a == 0 || b == 0)
return 1;
int x = a & b;
if (a == x || b == x)
return 1;
return 2;
}
public static void main(String[] args)
{
int a = 5, b = 12;
int result = solve(a, b);
System.out.println(result);
}
}
|
Python3
def solve(a, b):
if a == b:
return 0
if a == 0 or b == 0:
return 1
x = a & b
if a == x or b == x:
return 1
return 2
a = 5
b = 12
result = solve(a, b)
print(result)
|
C#
using System;
class GFG
{
static int Solve(int a, int b)
{
if (a == b)
return 0;
if (a == 0 || b == 0)
return 1;
int x = a & b;
if (a == x || b == x)
return 1;
return 2;
}
static void Main(string[] args)
{
int a = 5, b = 12;
int result = Solve(a, b);
Console.WriteLine(result);
Console.ReadLine();
}
}
|
Javascript
function solve(a, b) {
if (a === b)
return 0;
if (a === 0 || b === 0)
return 1;
let x = a & b;
if (a === x || b === x)
return 1;
return 2;
}
let a = 5;
let b = 12;
let result = solve(a, b);
console.log(result);
|
Time Complexity: O(1), as it takes constant time.
Auxiliary space: O(1), as it uses constant space.
|
