0
$\begingroup$

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;
}
$\endgroup$
2
  • 1
    $\begingroup$ 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. $\endgroup$
    – hardmath
    Jun 26 '17 at 21:39
  • 1
    $\begingroup$ 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$. $\endgroup$
    – hardmath
    Jun 27 '17 at 0:12
0
$\begingroup$

It is not an answer, but rather an extended comment.

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.

$\endgroup$
0
$\begingroup$

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.

Being close to a square may be another place where greedy is sub-optimal. For example 83, 123, 147, 171 where the greedy approach has the same number of steps as step-to-nearest square approach. I suspect with more searching a square would be found that has fewer steps with later approach.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.