1

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);
ѺȐeallү
  • 2,887
  • 3
  • 22
  • 34
  • 1
    Which performance problems are you experiencing with your solution? I mean, it does not even run because numbers don't have a `split` method. Can't get faster than that :P – Felix Kling May 15 '14 at 22:32
  • Is the targetNumber any number, or always a single digit? What do you mean by occurrences? – Hamza Kubba May 15 '14 at 22:32
  • If you care for effeciency, just don't use a loop. – Bergi May 15 '14 at 22:44
  • @FelixKling fixed...I just want to know the fastest way. :) – ѺȐeallү May 15 '14 at 22:53
  • Surely somebody a little better at elementary number theory than me can come up with a closed-form solution to this problem. (Or something pretty close.) – Pointy May 15 '14 at 22:56
  • Well, in the numbers between zero and 100 (`[0,100)`), one encounters 21 sevens: `07, 17, 27, 37, 47, 57, 67, 77, 87, 97, 70, 71, 72, 73, 74, 75, 76, 78, 79`. I think that in a range from 0 to any power of 10, it's something like `log10(max) * 10 + log10(max) - 1` – Pointy May 15 '14 at 23:07
  • wait that's not quite right; the second part is more complicated and is probably a combinatorial term. – Pointy May 15 '14 at 23:08
  • @Pointy: I count 20 sevens in that string. – Bergi May 15 '14 at 23:22
  • @Bergi I have a lifelong awful track record of off-by-one errors :) – Pointy May 15 '14 at 23:25
  • @Pointy Yeah with the provided example numbers the answer should return a count of 20. Good catch! :) – ѺȐeallү May 15 '14 at 23:27

3 Answers3

4

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);
     }
}
Bergi
  • 630,263
  • 148
  • 957
  • 1,375
1

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)

Community
  • 1
  • 1
juvian
  • 15,875
  • 2
  • 37
  • 38
  • Thanks for the link, it helped me figure out a correct solution. Also I've used the same solution for coping with the `min` parameter :-) – Bergi May 16 '14 at 02:02
  • @juvian: Have a look at the third revision of my answer above :-) – Bergi May 16 '14 at 03:23
0

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...

ѺȐeallү
  • 2,887
  • 3
  • 22
  • 34