Introduction
This blog finds the minimum number of operations needed to make two numbers equal by multiplying with their prime factors.
Problem Statement
The problem states that given two positive integers ‘a’ and ‘b’, We have to make both ‘a’ and ‘b’ equal in the minimum number of operations.
In one operation:-
- Take any one of the given integers, let say ‘a’.
- Choose any prime factor of a, let say ‘x’.
- Update ‘a’ with a*x i.e a=a*x.
We have to find a minimum number of operations needed to make two numbers equal. If we cannot make both integers equal then print -1.
Let's take some examples to understand this problem better.
Sample Examples
Example 1:
Given Integers: a = 150, b = 180
Output - 3
Explanation:
Operation 1- Select integer ‘a’ and multiply with 3(because 3 is the prime factor of a) then a*3= 450 and b=180
Operation 2- Select integer ‘a’ and multiply with 2(because 2 is the prime factor of a) then a*2= 900 and b=180
Operation 3- Select integer ‘b’ and multiply with 5(because 5 is the prime factor of b) then a = 900 and b*5=900
Example 2:
Given Integer: a=10, b=15
Output - 1
Explanation:
We cannot make both a and b equal because, in the prime factor of a = 2*5 and b=3*5, we cannot bring 3 in ‘a’ by multiplying with its own prime factor.
Also see, Euclid GCD Algorithm
Approach
In this problem, we have to find the minimum number of operations needed to make two numbers equal by multiplying with their prime factors. If it is not possible then print -1.
First, we have to check it is possible to make ‘a’ and ‘b’ equal or not. ’a’ and ‘b’ is written as:
a =p1^a1*p2^a2*p3^a3.......*pn^an
b =q1^b1*q2^b2*q3^b3.......*qm^bm
Where p1,p2,p3…pn are prime factors of ‘a’ and q1,q2,q3,....qm are prime factors of ‘b’.
If any pi prime factors of ‘a’ are not present in the prime factors of ‘b’ or any qi prime factors of ‘b’ are not present in the prime factors of ‘a’ then we cannot make ‘a’ and ‘b’ equal because we cannot bring that factor by multiplying with their own prime factors.
If every prime factor of ‘a’ is present in ‘b’ and every prime factor of ‘b’ is present in ‘a’ then the answer will be the sum of absolute difference in the count of prime factors in ‘a’ and ‘b’.
If p1 < p2 < p3.....< pn and q1 < q2 < q3....< qm, where n = m because all prime factors of ‘a’ present in ‘b’ and all prime factors of ‘b’ present in ‘a’.
ans = mod(a1-b1)+ mod(a2-b2)+ mod(a3-b3).....+ mod(an-bn)
Pseudo code
// Make two numbers equal by multiplying with their prime factors
int operations(int a, int b)
int ans =0
Map1 = prime_factor(a); // Map1 stores count of each factor of a
Map2 = prime_factor(b); // Map2 stores count of each factor of b
if -> every prime factor of ‘a’ is not present in ‘b’
return -1
if -> every prime factor of ‘b’ is not present in ‘a’
return -1;
loop(every factor of ‘a’)
ans = ans + mod(Map1.count(factor)-Map2.count(factor))
return ans;
306+ registered