include

include

include

include

include

include

include

using namespace std;

int testCase(int n) { if (n == 0) { return 0; }

priority_queue<int, vector<int>, greater<int>> pq;
unordered_map<int, int> moves;

pq.push(n);
moves.insert(make_pair(n, 0));

int minMoves = 1e9;
while (!pq.empty()) {
    int x = pq.top();
    int m = moves.find(x)->second;
    pq.pop();

    if (x > 0 && m + 1 < minMoves) {
        auto it = moves.insert(make_pair(x - 1, 1e9)).first;
        if (it->second > m + 1) {
            it->second = m + 1;
            pq.push(x - 1);
            if (x - 1 == 0) {
                minMoves = it->second;
            }
        }
        for (int k = (int)floor(sqrt(x)); k > 1; k--) {
            if (x % k == 0) {
                int factor = x / k;
                auto it2 = moves.insert(make_pair(factor, 1e9)).first;
                if (it2->second > m + 1) {
                    it2->second = m + 1;
                    pq.push(factor);
                }
            }
        }
    }
}

return minMoves;

}

int main() { int q; cin >> q;

for (int i = 0; i < q; i++) {
    int n;
    cin >> n;
    cout << testCase(n) << endl;
}

return 0;

}

how is editorial code working q =10^5 n =10^6

for each query we are doing memset so q*n then how is it working or is there anything that i am missing here

TESTCASES ARE WRONG. DONT BE SURPRISED. e.g: for 86 expected output is 7. but my output was 8: 86->43->42->7->6->3->2->1->0.!

js

const map = { 0: 0, 1: 1 };
function downToZero(n) {
    for (let i = 2; i <= n; i++) {
        if (map[i]) continue;

        let a = 2;
        let min = map[i - 1];
        let b;
        while (a <= (b = i / a)) {
            if (Math.floor(b) === b) {
                min = Math.min(min, map[b]);
            }
            a++;
        }
        map[i] = min + 1;
    }
    return map[n];
}

Here is my DP solution (C# code). Take a look:

public static int DownToZero(int n) {
    return new DownToZeroSolution().Solve(n);
}
    
class DownToZeroSolution {
    static int calculated_N;
    static readonly int[] solutions;

    static DownToZeroSolution() {
        calculated_N = 1;
        solutions = new int[1_000_001];
        solutions[1] = 1;
    }
    public int Solve(int n) {
        if(n <= calculated_N) return solutions[n];

        for(int i = calculated_N + 1; i <= n; i++) {
            solutions[i] = CalculateItem(i);
        }
        calculated_N = n;
        return solutions[n];
    }
    static int CalculateItem(int n) {
        int min = solutions[n - 1];
        int d_start;
        int d_step;

        if((n & 1) == 1) {
            d_start = 3;
            d_step = 2;
        }
        else {
            d_start = 2;
            d_step = 1;
        }
        
        int topN = (int)(Math.Sqrt(n) + 0.1);

        // n = d1*d2
        for(int d1 = d_start; d1 <= topN; d1 += d_step) {
            if(n % d1 == 0)
                min = Math.Min(min, solutions[Math.Max(d1, n / d1)]);
        }
        return 1 + min;
    }
}