javascript - 编写一个接受整数 n 的函数，并计算 0 和 n 之间有多少个整数包含 5

Question

我正在尝试解决这个问题，并且我知道解决 0 数量的方法，但无法解决 5 数量的问题我正在尝试这样的事情

  function findFive(lastNumber){

        var count=1,k;
        if(lastNumber<5)
            return 0;
        else if(lastNumber===5)
            return 1;
        else{

            for(var i=6;i<=lastNumber;i++){
                k=i;
                while(k>0){

                    if(k%5==0 && k%10!==0)
                        count++;
                        k=k/5;
                }
            }
            return count;
        }
    }

但这不适用于 50、550、500 等数字。所以我想知道哪种方法是解决这个问题的最佳且有效的方法。

谢谢。任何帮助表示赞赏

Answer 1

随着数字不断增加，我们可以看到总数的模式。

1    -- 0
5    -- 1
10   -- 0 * 9   + 10^0 = 1
59   -- 1 * 5   + 10^1    
60   -- 1 *(6-1)+ 10^1
100  -- 1 * 9   + 10^1 = 19
599  -- 19* 5   + 10^2
600  -- 1 *(6-1)+ 10^2
1000 -- 19* 9   + 10^2 = 271 

通过这种模式，我们可以通过查看数字中的每个数字来获得结果例如:

332    -- 3*19 + 3*1 + 2*0 
984    -- [(9-1)*19 + 100] + [(8-1)*1 + 10] + [4*0]
3943   -- 3*271 + ((8-1)*19 + 100) + 4*1 + 3*0
1543   -- 1*271 + (5*1 +44) 

然后我们就可以编写一些代码了。

function findFive(n){
    // we'll cast the value to a string, to be able to grab the Most Significant Digit easily
    return _findFive(String(n))["t"]    
}
// helper function. Returns the integer value of the number without 
// the first digit (eg. "3948" returns 948)
function remaining(n){                      
    return n.length > 1 ? parseInt(n.substr(1)) : 0;
}

// Recursive function. Returns the total number of 5s in the range 0 to n, and the multiplier for the next higher digit
function _findFive(n){
    if(n.length == 0) return {t:0,m:0};
    var result = _findFive(n.substr(1));    // get the total from the less significant digits. 
                                            // Also returns the multiplier for the MSD
    var msd = n[0];                         // Most significant digit
    if(msd < 5)         total = msd * result["m"] + result["t"];
    else if(msd == 5)   total = msd * result["m"] + remaining(n) + 1;
    else                total = (msd-1) * result["m"] + Math.pow(10,n.length-1) + result["t"];

    var multiplier = result["m"]* 9 + Math.pow(10,n.length-1);  // calculate multiplier for next higher digit
    return {t:total,m:multiplier}   
}

这段代码将在 log(n) 时间内解决问题。无需处理范围内的每个数字(O(n) 时间)即可获得答案。