BigInt Оптимизация

Question

Мне необходимо вычислить общее количество цифр в последовательности чисел от 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. В целом, пока что, вызывают проблемы только задачи с оптимизацией.

Answer 1

Just paste on your code with help math lib

Answer 2

Для того, чтобы посчитать цифры, не нужно генерировать сами числа, 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))

БЛОГ НА HUSL

BigInt Оптимизация

Ответы (2 шт):