# How to Make X to 0 in minimum number of steps?

You are given a number X. You can perform any of the two operations on X in each move:

1. If we take two integers a and b, such that X is a product of a and b (a != 1, b != 1), then we can modify X = max(a, b).

2. Decrement the value of X by 1.

Find out the minimum number of moves required to reduce X to 0.

What I have tried is greedy approach. I factorized the number closest to its square root, and then proceed backwards. If the number is prime, I just do -1. Is this approach correct?

My approach to this question:

// Author - Rajat Saxena (bloodphoenix)
#include <bits/stdc++.h>
#define M           1000000007
#define nl          cout << endl
#define pb          push_back
#define F           first
#define S           second
#define stuff(a,v)  memset(a,v,sizeof a)
#define whatis(x)   cout << #x << " = " << x << endl
#define FAST        ios_base::sync_with_stdio(false);cin.tie(NULL);
using namespace std;
template <typename T1, typename T2>
std::ostream& operator <<(std::ostream &os, const map<T1,T2> &m)
{
for (const auto &p : m)
{
os << p.first << "->" << p.second << endl;
}
return os;
}
template <typename T1>
void printData(const T1 &data)
{
for (auto i = begin(data) ; i != end(data) ; ++i)
{
cout << *i << " ";
}
cout << endl;
return;
}
// Date - 27 June 2017 (Tuesday) 01:50 AM

int dp[1000006];

int main(int argc, char const *argv[])
{
FAST
stuff(dp,-1);
dp[0] = 0;
dp[1] = 1;
dp[2] = 2;
dp[3]= 3;
for (int i = 4; i < 1000001; ++i)
{
int d = sqrt(i);
int ans = INT_MAX;
bool flag = false;
for (int j = d; j >= 2; --j)
{
if(i%j == 0)
{
ans = min(ans,dp[max(j,i/j)]);
flag = true;
}
}

if(flag)
dp[i] = 1 + ans;
else
dp[i] = 1 + dp[i-1];
}

int t; cin >> t;
while(t--)
{
int x; cin >> x;
cout << dp[x] << endl;

}
return 0;
}

• What exactly are you asking is "correct"? Since you have defined the rules, presumably you are asking either about correctly finding the shortest path from $X$ to $0$, or about the code being correct. I don't know why the code was included, but checking your programming is off-topic here. Jun 26 '17 at 21:39
• Certainly when $X$ is prime we will use the $-1$ rule, and plausibly one can avoid that rule except when $X$ is prime. However the choice of "nearest to square root" for composite  is not optimal, e.g. $X=60$. Then $X=12*5$ is better than $X=10*6$. Jun 27 '17 at 0:12

The method is not right. Take $258$. Your approach gives $258, 43, 42, 7, 6, 3, 2, 1, 0$, totaling $8$ moves.
On the other hand, $258, 257, 256, 16, 4, 2, 1, 0$ is $7$ moves.
Your approach is not optimal in all cases. For the case of 59, the greedy progression of $59, 58, 29, 28, 7, 6, 3, 2, 1, 0$ is 9 steps. But $59,58,57,56,8,4,2,1,0$ is 8 steps. In general if $x$ is close to a number that has a factor of $2^n$, where is n is say 3 or more, then the greedy approach may be sub-optimal.