Посчитать кол-во 9 в числах от 1 до n (нужен оптимизированный код)
Всем добрый день.
Все мы хорошо помним школьную задачку: посчитать, сколько раз встречается 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? Какие есть ещё варианты решения подобных задач с перебором, но более оптимальных? Или, может, просто я совсем нелепое решение придумал? Спасибо за ваши варианты |
Цитата:
Цитата:
|
Цитата:
|
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))
|
Вообще задачи с codewars стоит самому решать.
Тем вы и учитесь Данная задача решается без строковых функций Делением на 10 и остаток 9 (a%10 ===9) рони, присоединяйся https://www.codewars.com там есть чем потренировать свои знания |
Vlasenko Fedor,
:) :thanks: |
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));
|
Alexandroppolus,
да код проходит тесты https://www.codewars.com/kata/551431...ain/javascript но это вы сделали, а не vlad_kl,:nono: там есть много интересных задач |
Цитата:
4 и более сам решать будет ) Цитата:
|
| Часовой пояс GMT +3, время: 10:49. |