0

Мне необходимо вычислить общее количество цифр в последовательности чисел от 1 до pages.

То есть если pages = 4, ответ будет 4, так как 1, 2, 3, 4 - ответ 4.

Если pages = 12, ответ - 15, так как 1-9 - по одной цифре в числе, 10-12 - по 2.

Надеюсь, что объяснил понятно, ссылку на задачу приложу.

function pageDigits(pages) {
  let digit1 = [0n]
  let i = 1n
  for (i; i <= pages; i++) {
    digit1[0] += BigInt(i.toString().length)
  }
  return digit1.join('')
}

Я пытался через такой цикл for, пробовал создавать массив и применять к нему map.

И все равно всегда упирался в производительность - код должен выполняться не более, чем за 12 секунд (12000 ms).

Пытался найти какие то способы оптимизации циклов с BigInt, но не нашел.

P.S. Я учу JS только 2 месяца, сейчас на CodeWars почти добил 4 kyu. В целом, пока что, вызывают проблемы только задачи с оптимизацией.

2
  • 1
    Переведите вопрос на русский. Тем более, что английский вариант не даёт четкого понимания, что именно нужно вычислить.
    – MBo
    5 апр 2022 в 0:30
  • Да и ссылку на задачу можно приложить. Есть надежда что там формулировка понятнее
    – Alexey Ten
    5 апр 2022 в 4:38

1 ответ 1

1

Для того, чтобы посчитать цифры, не нужно генерировать сами числа, BigInt может понадобиться только для ответа - количества цифр s, и для переменной t (ниже).

Заметим, что для чисел до 10 общее количество цифр 9, до 100 - добавляется 180, до 1000 - ещё 2700 цифр, и так далее.

Будем хранить количество цифр в одном числе dig для текущего диапазона, и степень десятки t, и пройдём все десятичные диапазоны, пока не дойдём до степени десяти, бОльшей заданного числа. Потом сделаем поправку на неиспользованные цифры (для заданного числа 997 мы посчитали цифры до 1000-1, значит, нужно отнять количество цифр в 998 и 999).

Код на Python, но, зная идею, на JS нетрудно написать

def countDigits(n):
    t = 1
    dig = 1
    s = 0
    while t <= n:
        s += dig * 9 * t
        dig += 1
        t *= 10

    s-= (t - 1 - n) * (dig - 1)
    return s

На JS я с BigInt обращаться не умею, перевел, как попало, лишь бы заработало:

function pageDigits(pages) {
  let pagesn = BigInt(pages)
  let s = 0n
  let t = 1n
  let dig = 1n
  while (t <= pagesn) {
        s += dig * 9n * t
        dig += 1n
        t *= 10n
  }
  s-= (t - 1n - pagesn) * (dig - 1n)
  return s
}  

console.log("" + pageDigits(12))
console.log("" + pageDigits(262144))

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.