【Edibat 算法 ★★★★★★】【吸血鬼数字】Vampire Numbers-Toy模板网

这篇具有很好参考价值的文章主要介绍了【Edibat 算法 ★★★★★★】【吸血鬼数字】Vampire Numbers。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

Vampire Numbers

recursion permutation brute force

A Vampire Number is a positive integer greater than 99, that rearranged in all of its possible digits permutations, with every permutation being split into two parts, is equal to the product of at least one of its permutations.

If the number has an even quantity of digits, left and right parts will have the same length in every permutation;

If the number has an odd quantity of digits and at least three digits, the left and right parts will present different lengths for every possible permutation, alternating between them in the range +1 and -1.

Given a positive integer n, implement a function that returns the type of n as a string:文章来源地址https://www.toymoban.com/news/detail-723713.html

'Normal Number' if n is lower than 100 or if no permutations return a product of their parts equal to n.

'Pseudovampire' if n it is a Vampire with an odd quantity of digits.

'True Vampire' if n it is a Vampire with an even quantity of digits.

Examples

isVampire(1260) // "True Vampire"
// Has an even number of digits and is greater than 99)
// Permutations:
// 12 * 60 = 720
// 16 * 20 = 320
// 10 * 26 = 260
// 21 * 60 = 1260

isVampire(126) // "Pseudovampire"
// Has an odd number of digits and is greater than 99
// Permutations:
// 12 * 6 = 72
// 1 * 26 = 26
// 21 * 6 = 126

isVampire(67) // "Normal Number"
// Is lower than 100
// Permutations:
// 6 * 7 = 7 * 6 = 42

Notes

Trivially, a number from 1 to 99 is a Normal Number by the definitions: a single-digit number can’t be split into two parts, and the product of the permutated two digits of a number will always be lower than the number itself.

Solutions

// solution1: recursion + permutation
const isVampire = (n) => {
    if(n < 100){
        return 'Normal Number'
    }
    let t = n,d=[];
    while(t){
        d.unshift(t%10)
        t = Math.floor(t/10)
    }
    let o = d.length&0b1;
    let res = compute(d,0,n,o,d.length)
    return res?(!o?'True Vampire':'Pseudovampire'):'Normal Number';
}
const compute = (d,k,n,o,l)=>{
    if(k==l){
        k = l>>>1
        let pair = toIntPair(d,k);
        let res = pair[0]*pair[1] === n;
        if(o && !res){
            pair = toIntPair(d,k+1);
            res = pair[0]*pair[1] === n;
        }
        return res;
    }
    for(let i=k;i<l;i++){
        [d[i],d[k]] = [d[k],d[i]]
        let res = compute(d,k+1,n,o,l)
        if(res){
            return true;
        }
        [d[k],d[i]] = [d[i],d[k]]
    }
    return false;
};
const toIntPair=(d,k)=>{
    let res = [0,0];
    for(let i=0;i<k;i++){
        res[0] = res[0]*10 + d[i]
    }
    for(let i=k;i<d.length;i++){
        res[1] = res[1]*10 + d[i]
    }
    return res
}

// solution2: brute force
const isVampire = (n) => {
    if(n < 100){
        return 'Normal Number'
    }
    let t = n,c=0;
    while(t){
        c++;
        t = Math.floor(t/10);
    }
    let o = c&0b1;
    c >>>= 1
    let max = 1 ;
    while(c-->0){
        max *= 10
    }
    let d=Array(10).fill(0);
    for(let i = Math.floor(max/10); i < max;i++){
            let j = Math.floor(n/i);
            let m = i*j;
            let [ii,jj,mm] = [i,j,m];
            while(mm){
                d[mm%10]++;
                mm = Math.floor(mm/10);
            }
            while(ii){
                d[ii%10]--;
                ii = Math.floor(ii/10);
            }
            while(jj){
                d[jj%10]--;
                jj = Math.floor(jj/10);
            }
            let is = true;
            for(let i=0;i<10;i++){
                if(d[i]){
                    is = false;
                    d[i] = 0;
                }
            }
            if(is && m === n){
                return !o?'True Vampire':'Pseudovampire';
            }
    }
    return 'Normal Number';
}

TestCases


let Test = (function(){
    return {
        assertEquals:function(actual,expected){
            if(actual !== expected){
                let errorMsg = `actual is ${actual},${expected} is expected`;
                throw new Error(errorMsg);
            }
        }
    }
})();

Test.assertEquals(isVampire(1260), "True Vampire", "Example #1")
Test.assertEquals(isVampire(126), "Pseudovampire", "Example #2")
Test.assertEquals(isVampire(67), "Normal Number", "Example #3")
Test.assertEquals(isVampire(1), "Normal Number")
Test.assertEquals(isVampire(645), "Normal Number")
Test.assertEquals(isVampire(688), "Pseudovampire")
Test.assertEquals(isVampire(1345), "Normal Number")
Test.assertEquals(isVampire(1395), "True Vampire")
Test.assertEquals(isVampire(12964), "Pseudovampire")
Test.assertEquals(isVampire(98765), "Normal Number")
Test.assertEquals(isVampire(124421), "Normal Number")
Test.assertEquals(isVampire(125460), "True Vampire")