Question:
Given 2 integers N and M. Convert a number N to M using minimum number of given operations.
The operations are:
Contrants:
N, M <= 10^9
Example:
N = 12, M = 18
The minimum operations are:
My take:
I'm trying to use BFS to solve this problem. For each number, the available edges to other numberers are the operations. But it got Time Limit Exceeded. Is there any better way to solve this?
Here is my BFS code:
queue<pair<int,int> > q;
vector<long long> pr;
ll m,n;
bool prime[MAXN+1];
void solve()
{
while (!q.empty())
{
pii x=q.front();
q.pop();
if (x.first==m)
{
cout << x.second;
return;
}
if (x.first==1) continue;
for(ll k:pr)
{
if (k>x.first) break;
if (x.first%k==0) q.push({x.first/k,x.second+1});
}
q.push({x.first*x.first,x.second+1});
}
}
The algorithm uses the decomposition on N and M in prime factors, keeping trace of the corresponding exponents.
If M has a prime factor that N does not have, there is no solution (the code returns -1).
If N has some prime factors that M doesn't have, then the first step is to divide N by these primes.
The corresponding number of operations is the sum of the corresponding exponents.
At this stage, we get two arrays A and B corresponding to the exponents of the common prime factors, for N and M.
It is worth noting that at this stage, the values of the primes involved is not relevant anymore, only the exponents matter.
Then one must determine the minimum number of squares (= multiplications by 2 of the exponents).
The is the smallest k such that A[i] >= 2^k B[i] for all indices i.
The number of multiplications is added to the number of operations only once, as all exponents are multiplied by 2 at the same time.
Last step is to determine, for each pair (a, b) = (A[i], B[i]), the number of subtractions needed to go from a to b, while implementing exactly k multiplications by 2. This is performed with the following rules:
- if (k == 0) f(a, b, k) = a-b
- Else:
- if ((a-1)*2^k >= b: f(a, b, k) = 1 + f(a-1, b, k)
- else: f(a, b, k) = f(2*a, b, k-1)
The complexity is dominated by the decomposition in primes factors: O(sqrt(n))
Code:
This code is rather long, but a great part consists if helper routines needed for debugging and analysis.
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
void print (const std::vector<int> &v, const std::string s = "") {
std::cout << s;
for (auto &x: v) {
std::cout << x << " ";
}
std::cout << std::endl;
}
void print_decomp (int n, const std::vector<int> &primes, const std::vector<int> &mult) {
std::cout << n << " = ";
int k = primes.size();
for (int i = 0; i < k; ++i) {
std::cout << primes[i];
if (mult[i] > 1) std::cout << "^" << mult[i];
std::cout << " ";
}
std::cout << "\n";
}
void prime_decomp (int nn, std::vector<int> &primes, std::vector<int> &mult) {
int n = nn;
if (n <= 1) return;
if (n % 2 == 0) {
primes.push_back(2);
int cpt = 1;
n/= 2;
while (n%2 == 0) {n /= 2; cpt++;}
mult.push_back (cpt);
}
int max_prime = sqrt(n);
int p = 3;
while (p <= max_prime) {
if (n % p == 0) {
primes.push_back(p);
int cpt = 1;
n/= p;
while (n%p == 0) {n /= p; cpt++;}
mult.push_back (cpt);
max_prime = sqrt(n);
}
p += 2;
}
if (n != 1) {
primes.push_back(n);
mult.push_back (1);
}
print_decomp (nn, primes, mult);
}
// Determine the number of subtractions to go from a to b, with exactly k multiplications by 2
int n_sub (int a, int b, int k, int power2) {
if (k == 0){
if (b > a) exit(1);
return a - b;
}
//if (a == 1) return n_sub (2*a, b, k-1, power2/2);
if ((a-1)*power2 >= b) {
return 1 + n_sub(a-1, b, k, power2);
} else {
return n_sub (2*a, b, k-1, power2/2);
}
return 0;
}
// A return of -1 means no possibility
int n_operations (int N, int M) {
int count = 0;
if (N == M) return 0;
if (N == 1) return -1;
std::vector<int> primes_N, primes_M, expon_N, expon_M;
// Prime decomposition
prime_decomp(N, primes_N, expon_N);
prime_decomp (M, primes_M, expon_M);
// Compare decomposition, check if a solution can exist, set up two exponent arrays
std::vector<int> A, B;
int index_A = 0, index_B = 0;
int nA = primes_N.size();
int nB = primes_M.size();
while (true) {
if ((index_A == nA) && (index_B == nB)) {
break;
}
if ((index_A < nA) && (index_B < nB)) {
if (primes_N[index_A] == primes_M[index_B]) {
A.push_back(expon_N[index_A]);
B.push_back(expon_M[index_B]);
index_A++; index_B++;
continue;
}
if (primes_N[index_A] < primes_M[index_B]) {
count += expon_N[index_A];
index_A++;
continue;
}
return -1; // M has a prime that N doesn't have: impossibility to go to M
}
if (index_B != nB) { // impossibility
return -1;
}
for (int i = index_A; i < nA; ++i) {
count += expon_N[i]; // suppression of primes in N not in M
}
break;
}
std::cout << "1st step, count = " << count << "\n";
print (A, "exponents of N: ");
print (B, "exponents of M: ");
// Determination of the number of multiplications by two of the exponents (= number of squares)
int n = A.size();
int n_mult2 = 0;
int power2 = 1;
for (int i = 0; i < n; ++i) {
while (power2*A[i] < B[i]) {
power2 *= 2;
n_mult2++;
}
}
count += n_mult2;
std::cout << "number of squares = " << n_mult2 << " -> " << power2 << "\n";
// For each pair of exponent, determine the number of subtractions,
// with a fixed number of multiplication by 2
for (int i = 0; i < n; ++i) {
count += n_sub (A[i], B[i], n_mult2, power2);
}
return count;
}
int main() {
int N, M;
std::cin >> N >> M;
auto ans = n_operations (N, M);
std::cout << ans << "\n";
return 0;
}