Посчитать кол-во 9 в числах от 1 до n (нужен оптимизированный код)

[vlad_kl]

Всем добрый день.
Все мы хорошо помним школьную задачку: посчитать, сколько раз встречается 9 во всех числах от 1 до 100. Ответ: 9, 19, 29, 39, 49, 59, 69, 79, 89, 90-99. Итого от 1 до 100 девятка встречается 20 раз.

Аналогичную задачку нашёл на codewars. Решить её несложно, есть много разных вариантов... НО по условиям задачи код должен выполняться быстро даже для 10 млрд. итераций. В моём случае при 5 млн. итераций - выполнение ~3 сек. Ну а за 100 млн. я уже вообще молчу, не говоря о 10 миллиардах. Ограничение codewars = 12 секунд на выполнение функции


Вариант 1

function number9(n) {
    let count = 0;
    for (let i = 1; i <= n; i++) {
        i = i.toString().split('');
        count += i.filter( el => el === '9').length;
        i = i.join('');
    }
    return count;
}

Вариант 2

function number9(n) {
    let count = 0;
    for (let i = 1; i <= n; i++) {
        if (i.toString().match(/9/g) === null) continue;
        count += i.toString().match(/9/g).length;
    }
    return count;
}

И тут, собственно, возник вопрос, а что есть быстрее цикла в JS? Какие есть ещё варианты решения подобных задач с перебором, но более оптимальных?
Или, может, просто я совсем нелепое решение придумал?

Спасибо за ваши варианты

[рони]

что есть быстрее цикла в JS?

ничего.

Какие есть ещё варианты решения подобных задач с перебором,

откажитесь от перебора - вычислите результат одной строкой

[vlad_kl]

откажитесь от перебора - вычислите результат одной строкой

А можно поконкретней, что вы имели в виду?

[рони]

vlad_kl,
наверняка есть формула по которой можно рассчитать а не перебирать.

[рони]

vlad_kl,
условно для чисел 10, 100, и т.д.

function number9(n) {
    let count = 0;
    for (let i = 1; i <= n; i++) {
        i = i.toString().split('');
        count += i.filter( el => el === '9').length;
        i = i.join('');
    }
    return count;

}
function test(n) {
   let {length} = n.toString();
   return --length * Math.pow(10, --length)
}

console.log(number9(100000), test(100000))

[Vlasenko Fedor]

Вообще задачи с codewars стоит самому решать.
Тем вы и учитесь
Данная задача решается без строковых функций
Делением на 10 и остаток 9 (a%10 ===9)
рони,
присоединяйся https://www.codewars.com там есть чем потренировать свои знания

[рони]

Vlasenko Fedor,

[Alexandroppolus]

function number9(n) {
  var count = 0;
  var p10count = 0;
  var p10 = 1;
  var m = n, prev = 0;
  while (m > 0) {
    var dig = m % 10;
    count = count + (dig === 9 ? prev + 1 : 0) + dig * p10count;
    m = Math.floor(m / 10);
    prev = prev + dig * p10;
    p10count = p10count * 10 + p10;
    p10 = p10 * 10;
  }
  return count;
}

alert('1234: ' + number9(1234));

[Vlasenko Fedor]

Alexandroppolus,
да код проходит тесты
https://www.codewars.com/kata/551431...ain/javascript
но это вы сделали, а не vlad_kl,
там есть много интересных задач

[Alexandroppolus]

но это вы сделали, а не vlad_kl

да и хрен с ним, задача-то на 5kyu всего, на хлеб не намажешь.
4 и более сам решать будет )

там есть много интересных задач

знаю, знаю..