Как найти «счастливые» билетики (числа) с помощью JavaScript?

Question

[Leatington]

Задали в универе задачку:

Подсчитать, сколько n-значных чисел имеют равную сумму первой половины
и второй половины цифр ("счастливые" числа). Число n является четным.
Например, для n = 6 числа "001010", "112220", "000000" счастливые.

Вот пример как должно быть:


Я написал следующий код, но, всё равно что-то не то...

function getLuckyTicketsCount(n){
    let count = 0;
  
    for (let i = 1; i<Math.pow(10,n);i++)
  {
    let s = String(i);
        let l = s.length;

    if ((l % 2) !== 0)
    {
      l++;
      s = s + '0';
    }
    
        let str1 = s.substr(0, l/2).split('');
        let str2 = s.substr(l/2, l).split('');
        let [sum1, sum2] = [0, 0];
    
        for (let k = 0; k<str1.length; k++)
    {
            sum1 = sum1+Number(str1[k]);
        }
        for (let k = 0; k<str2.length; k++)
    {
            sum2 = sum2+Number(str2[k]);
        }
        if (sum1 == sum2)
        {
            count++;
        }
    
    }
  
    return count
}

Comments

[Сергей Соколов]

Число n является четным.

А на скрине getLuckyTicketsCount(3) — нестыковочка!

Answer 1

[Сергей Соколов]

Можно для «половины» числа пробежаться и составить словарь { сумма: счётчик }, сколько раз каждая сумма встретилась на всём диапазоне 000..999 (для n = 6, т.е. половина = 3)
Сумма квадратов счётчиков даст общее число счастливых билетов.

Почему квадратов

Например, сумму 1 даёт 3 варианта (001, 010, 100). И для каждого из них в правой части билета может быть каждая из 3 комбинаций. Итого 3 * 3 = 9 вариантов билета с суммами 1 = 1.

function getLuckyTicketsCount(n) {
  const sums = {};
  for (let i = 0; i < Math.pow(10, n >> 1); i++) {
    // посчитать сумму цифр
    let sum = 0, d = i;
    while (d > 0) {
      sum += d % 10; // прибавили младшую цифру
      d = Math.floor(d / 10); // сдвинули число вправо на 1 цифру
    }

    // и в словарь прибавить 1 для этой суммы
    sums[sum] = (sums[sum] || 0) + 1;
  }

  return Object.values(sums) // счетчики суммм
    .map((n) => n * n) // квадраты
    .reduce((acc, c) => acc + c); // сложить все
}

Comments

[Alexandroppolus]

.map((n) => n * n) лишний, можно в редукторе acc + c*c

[Сергей Соколов]

Alexandroppolus, а, точно, забыл про i % 9! Пусть так остаётся, нагляднее )
Тут же в образовательных целях эт всё.

[Alexandroppolus]

Сергей Соколов, не, там ещё добавить что-то надо, i % 9 недостаточно..

[Сергей Соколов]

Alexandroppolus, сумма цифр числа i = (i - 1) % 9 + 1;

[Alexandroppolus]

Сергей Соколов, это всё остаток от деления суммы цифр на 9, а не сама сумма цифр. Что-то формула сходу не придумывается )

[Сергей Соколов]

Alexandroppolus, не, это именно сумма, но рекурсивная. Т.е. если после сложения получилось длинное число, надо снова сложить его цифры, пока не останется одна. Для 12345 (сумма 15) даст 6.

А в условии, похоже требуется нерекурсивная, обычная одноразовая сумма цифр.

[Alexandroppolus]

Сергей Соколов, да, "счастливые билетики" разумеются по одноразовой сумме. И тут всё сложнее. Видимо, без унылого цикла не обойтись )
рекурсивная, да, с %9 вычисляется, совсем недавно в алгоритмах спрашивали

[Роман]

Alexandroppolus, Сергей Соколов, что то мне подсказывает, что количество таких билетиков вычисляется по формуле

const result = Math.pow(10, n >> 1)

ps: но это не точно))))

psps: да действительно обманул. Не слабо так ошибся сокращая логику. Сейчас скину правильную)

[Роман]

Alexandroppolus, Сергей Соколов, сори, реально косякнул))))

Давным давно решал эту задачку, но сейчас формула совсем не выходит.

Завтра еще подумаю, может что и нарисуется, а сейчас совсем уже шарики за ролики. Помню только что там вся эта комбинаторика решалась через рекурсивное сложение арифметических прогрессий, которое можно было перевести в не очень хитрую формулу.

[Alexandroppolus]

Роман, подозреваю, что лаконичной формулы, которая не требует цикл для вычисления, тут не придумать. Интересно, можно ли вычислять за O(1), имея на руках предыдущие результаты? То есть, у нас N цифр, и хотим их сумму. В 9/10 всех случаев sum(k+1) = sum(k) + 1, но иногда придется бегать по девяткам справа, хотя "в среднем" примерно 1.11 раз, то есть это амортизированная O(1).

[Сергей Соколов]

Alexandroppolus, для 12345 первая сумма цифр равна остатку от деления на 18.
для 123451234 % 27 = 25 (первая сумма цифр)
Может, с этими остатками по модулям кратным 9 можно что-то придумать?