Untitled

 avatar
unknown
plain_text
4 months ago
2.1 kB
3
Indexable
var minOperations = function(n, m) {
    function sieve(x) {
        let y = Array(x + 1).fill(true);
        y[0] = y[1] = false;
        for (let i = 2; i * i <= x; i++) {
            if (y[i]) {
                for (let j = i * i; j <= x; j += i) {
                    y[j] = false;
                }
            }
        }
        return y;
    }

    let a = sieve(9999);
    if (a[n] || a[m]) return -1;

    let b = 0;
    let c = n;
    while (c > 0) {
        b++;
        c = Math.floor(c / 10);
    }
    if (n === 0) b = 1;

    const d = 10000;
    let e = Array(d).fill(Number.MAX_SAFE_INTEGER);
    e[n] = n;

    let f = [];
    f.push([n, n]);

    while (f.length > 0) {
        f.sort((x, y) => x[0] - y[0]);
        let g = f.shift();
        let h = g[0];
        let i = g[1];

        if (i === m) return h;

        if (h > e[i]) continue;

        let j = i.toString();
        while (j.length < b) j = "0" + j;

        for (let k = 0; k < b; k++) {
            let l = j[k];

            if (l < '9') {
                let m1 = j.slice();
                m1 = m1.substring(0, k) + (parseInt(l) + 1) + m1.substring(k + 1);
                if (m1[0] !== '0') {
                    let n1 = parseInt(m1);
                    if (!a[n1]) {
                        let o = h + n1;
                        if (o < e[n1]) {
                            e[n1] = o;
                            f.push([o, n1]);
                        }
                    }
                }
            }

            if (l > '0') {
                let m2 = j.slice();
                m2 = m2.substring(0, k) + (parseInt(l) - 1) + m2.substring(k + 1);
                if (m2[0] !== '0') {
                    let n2 = parseInt(m2);
                    if (!a[n2]) {
                        let o2 = h + n2;
                        if (o2 < e[n2]) {
                            e[n2] = o2;
                            f.push([o2, n2]);
                        }
                    }
                }
            }
        }
    }
    
    return -1;
};
Editor is loading...
Leave a Comment