def downToZero(n): if n == 0: return 0 queue = deque([(n, 0)]) visited = set([n])

while queue:
    current, moves = queue.popleft()        

    if current == 0:
        return moves

    # Operation 1
    if current - 1 not in visited:            
        queue.append((current - 1, moves + 1))
        visited.add(current - 1)

    # Operation 2
    for i in range(2, int(current**0.5) + 1):
        if current % i == 0:
            factor = max(i, current // i)
            if factor not in visited:
                queue.append((factor, moves + 1))
                visited.add(factor)

return -1

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];
}