CODEWITHSUNDEEP
javascriptperformanceloopsmathmathematical-optimization
ѺȐeallү
ѺȐeallү

Reputation: 3027

Javascript Loop Performance: Counting occurrences of a number in a finite series

What is the most efficient way to write a javascript loop to calculate the number of occurrences of 7's (as an example number) that will be encountered in counting from 1 to 100?

Example:

function numberOccurences(targetNumber, minNumber, maxNumber) {

var count = 0;
for (i = minNumber; i < maxNumber; i++) {
    count = count + (i.toString().split(targetNumber).length - 1);     
}
return count;
}

var result = numberOccurences(7,1,100);

Upvotes: 1

Views: 297

Answers (3)

Bergi
Bergi

Reputation: 664929

This will do it without looking at the actual numbers. Sorry, no loop, but you did ask for effeciency. If you really want to use a loop, make the recursion an iteration.

function digitOccurences(digit, min, max, base) {
    if (typeof base != "number") base = 10;
    return digitOccurencesPlus(digit, max, base, 1, 0) - digitOccurencesPlus(digit, min, base, 1, 0);

    function digitOccurencesPlus(digit, N, base, pow, rest) {
        if (N == 0) return 0;
        var lastDigit = N%base,
            prevDigits = (N-lastDigit)/base;
        var occsInLastDigit = pow*(prevDigits+(lastDigit>digit));
        var occsOfLastInRest = rest * (lastDigit==digit);
        // console.log(prevDigits+" "+lastDigit, rest, occsInLastDigit, occsOfLastInRest);
        return occsInLastDigit + occsOfLastInRest + digitOccurencesPlus(digit, prevDigits, base, pow*base, pow*lastDigit+rest);
     }
}

Upvotes: 4

ѺȐeallү
ѺȐeallү

Reputation: 3027

This is much faster (x6) than my original function...JSPERF

function numberOccurences2(targetNumber, minNumber, maxNumber) { 
var strMe = "";
for (i = minNumber; i < maxNumber; i++) {
    strMe = strMe.concat(i);
}
var re = new RegExp(targetNumber,"g");
var num1 = strMe.length;
var num2 = strMe.replace(re, "").length;
num2 = num1- num2;
return (num2);
}

There has to be a faster way still...

Upvotes: 0

juvian
juvian

Reputation: 16068

This is an interesting problem, and already has similar answers for other languages. Maybe you could try to make this one in javascript: Count the number of Ks between 0 and N

That solution is for occurences from 0 to n, but you could easily use it to calculate from a to b this way:

occurences(a,b)= occurences(0,b)-occurences(0,a)

Upvotes: 1

Related Questions