Решение задачи

[Himmelin]

Число называется счастливым, если его цифры расположены в неубывающем порядке и сумма цифр равна num. Количество цифр указано в параметре k. Необходимо найти все счастливые числа в диапазоне k (например: если k = 3, диапазон от 100 до 999). Ответ нужно дать в виде массива, который содержит количество счастливых чисел, первое и последнее счастливое число. В случае, если счастливые числа не найдены, возвращается массив с единственным элементом 0.

Примеры: luckyNumbers(10, 3) выведет [8, 118, 334];
luckyNumbers(27, 3) выведет [1, 999, 999].

Если кто-то с такой задачей сталкивался, подскажите, как решать.

[Alexandroppolus]

function getCount(n, k) {
    if (k < 1) return 0;
    const map = new Map();

    function calc(f, n, k) {
        if (n < f * k || n > 9 * k) {
            return 0;
        }
        if (k < 2) {
            return 1;
        }
        const key = `${f}_${n}_${k}`;
        const saved = map.get(key);
        if (saved != null) { return saved; }

        let count = 0;

        for (let i = f; i <= 9; ++i) {
            count += calc(i, n - i, k - 1);
        }

        map.set(key, count);

        return count;
    }

    return calc(1, n, k);
}

function getMin(n, k) {
    if (k < 1 || n < k || n > 9 * k) {
        return 0;
    }
    let r = 0;
    while (k > 1 && n - 1 <= 9 * (k - 1)) {
        r = r * 10 + 1;
        n--;
        k--;
    }
    k--;
    r = r * 10 + n - 9 * k;
    while (k > 0) {
        r = r * 10 + 9;
        k--;
    }
    return r;
}

function getMax(n, k) {
    if (k < 1 || n < k || n > 9 * k) {
        return 0;
    }
    const base = Math.floor(n / k);
    const head = k - n % k;
    let r = 0;
    for (i = 0; i < k; ++i) {
        r = r * 10 + base + (i < head ? 0 : 1);
    }
    return r;
}

function luckyNumbers(n, k) {
    const max = getMax(n, k);
    if (!max) return [0];

    return [getCount(n, k), getMin(n, k), max];
}

alert(luckyNumbers(10, 3));

[Himmelin]

Спасибо большое!

[Himmelin]

Можно уточнить, как вы пришли к такому решению? Какая-то формула математическая есть? Потому что я детально изучил решение и понял, что сам бы не смог придумать такие формулы.

[Alexandroppolus]

Да никакой особой формулы нет. Простые наблюдения. Максимальное число всегда будет иметь вид ААА...АВВВ...В, где В = А+1, потому что стремимся увеличить старшие разряды (которые слева). Аналогично, минимальное 111...1А999...9, здесь уменьшаем старшие разряды. Ты и сам можешь поэкспериментировать с числами и заметить это.

Для подсчета количества не требуется бежать циклом от минимального числа к максимальному и каждое проверять на соответствие условиям. Суммируем количества вариантов для всех значений старшего разряда. Если старший разряд равен f, то за ним стоит calc(f, n - f, k - 1) вариантов - потому что справа от него (k - 1) цифр, сумма которых равна (n - f), а в старшем разряде цифра не менее чем f. Ну и оптимизация в виде Map, потому что по факту будет много повторных расчетов, и ускорение от оптимизации весьма ощутимое.

[Himmelin]

Думаю стоит попробовать да с числами поиграться. Вот я как раз циклом пытался перебирать и очень много времени у меня это занимало, когда разрядов > 10 вообще помирал интерпретатор Моя проблема в том, что я мыслю только циклами и массивами в подобных задачах, надо пробовать по-другому думать начинать.