Как стать автором
Обновить

Комментарии 13

Подзадача: если n = 1, а k = числу, которое мы ищем - подзадача решена,
если нет - перебираем все числа (>= последнего) рекурсивно вызывая
подзадачу.

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

Количество вариантов считается банальной рекурсией, с мемоизацией. Ну то есть ДП, как верно сказал автор

Вот, на скорую руку. Проверил на нескольких значениях.

function calcCount(n, k) {
    const storage = new Map();

    function count(n, k, min) {
        if (k < 2) {
            return n < min || n > 9 ? 0 : 1;
        }
        if (n < min * k || n > 9 * k) {
            return 0;
        }
        
        const key = n + '_' + k + '_' + min;
        let r = storage.get(key);
        if (r == null) {
            r = 0;
            const max = Math.min(Math.ceil(n / k), 9);
            for (let i = min; i <= max; ++i) {
                r += count(n - i, k - 1, i);
            }
            storage.set(key, r);
        }
        return r;
    }

    return count(n, k, 1);
}

Вы правы, я сильно просчитался в сложности, 20 знаков действительно не большая проблема, это далеко не полный перебор.

Возможная ошибка, с которой столкнулся автор - числа больше MAX_SAFE_INTEGER(9007199254740991 или 16 символов) в js округляются, на конце получаются нули, похоже авторы задачи это не предусмотрели, в результате минимального и максимального значения должно быть или BigInt или строка.

Вряд ли там длинные числа. Условие гарантирует, что k не более 20. Возможные n при этом до 180, а результаты совсем копеечные - максимум ~61000 вариантов.

Я имел ввиду числа на выходе, в примерах это массив чисел, вариантов да, будет меньше, но при k >= 16 буду проблемы с минимальным и максимальным, даже если все считается правильно, ответ вряд ли засчитается:

> Number('11199999999999999')
11200000000000000

P. S. Перечитал условия задачи, там не зря сказано "приведенное к строке", только в примерах все равно числа

думаю практически все используют примеры в качестве тестов и подгоняют под них ответы.
будет уроком, что надо внимательно читать задание

Супер!!!!, для интереса переписал код, чтобы вместо чисел использовать строки (т.е. в формате [8, '118', '334']) и 80 из 80 баллов.
Почему-то не продумал о том, что int будет переполняться

Добрый день! Я Вика, рекрутер из Яндекса. Проверила список и не вижу, чтобы были участники, оставшиеся без обратной связи. Могли бы вы, пожалуйста, представиться? Или снова написать на почту поддержки?

А чего не написали на почту, указанную в письме со ссылкой на задачи? Тоже принимал участие, набрал похожее количество баллов, от Яндекса написали через пару дней. Дальнейшие шаги тоже прошел, оффер получил, но пока не принял. Со стороны Яндекса всё было очень даже приятно, никаких нареканий у меня нет. Может автору просто не повезло?

Я писал, но ответ получил уже после мероприятия. Не думаю что дело в везении.

Так и что в итоге ответили-то? На собеседование позвали? Молчание в нужный момент как-то объяснили? Имхо статью имело бы смысл проапгрейдить, а то получается, что продолжение истории было, а об этом - ни слова.

Если честно, я не видел особого смысла участвовать в мероприятии, после того как оно завершилось. Не стал отвечать, возможно это было ошибкой, кто знает

Сейчас учу джээс. Практики ради хотелось бы взглянуть на рабочие примеры ответов на задания контекста. Может есть у кого нибудь какие то ссылки на примеры??

Зарегистрируйтесь на Хабре, чтобы оставить комментарий

Публикации

Истории