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

Добро пожаловать! К новой статье Code Stories, где каждую неделю мы решаем интересные задачи, используя основы компьютерных наук. 🚀

Мы начнем с детального понимания постановки задачи.
После этого мы сосредоточимся на различных подходах к решению.
Наконец, мы закодируем решение. 🎉

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

Проблема ❓

Вам дано неотрицательное целое число N, которое может содержать не более 1000 цифр без начальных нулей. Наряду с целым числом K, которое является целым числом от 1 до 100.

Вы должны определить, можно ли удалить некоторые цифры (возможно, 0), чтобы результат содержал как минимум 1 цифру, образовывал неотрицательное целое число, не имел ведущих нулей и делился на K.

Обратите внимание, вы не можете переставлять цифры, которые остались после удаления.
Если решение существует, вы должны его распечатать. (Выведите любой, если несколько).

Стратегия 💡

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

Constraints:
1 ≤ lenght(N) ≤ 1000
1 ≤ K ≤ 100

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

Перед нами стоят 2 проблемы:

Работа с 1000-значным числом как целым числом

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

Вы можете возразить, что можете это сделать или использовать язык с поддержкой BIG INT. Достаточно честно! Давайте посмотрим на другое предостережение.

Генерация всех возможных вариантов решения

Нам разрешено удалить из числа определенное количество цифр, чтобы оно делилось на K.

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

Но вот в чем загвоздка. Идея создания всех кандидатов эквивалентна созданию подмножеств данного набора.

Say your N = 123
Now you want to generate candidate solutions by removing:
- 0 digits: 123 
- 1 digits: 23, 13, 12
- 2 digits: 1, 2, 3
NOTE: We can't remove all the 3 digits as per the questions

Как и выше, где у нас есть 2³-1 = 7 возможных решений, могут быть (2^lenght(N))-1 подмножества для любых N.

В худшем случае ваш модуль генерации подмножества будет отключен просто потому, что 2¹⁰⁰⁰ довольно велик!

На сколько большой? Обычно вы можете выполнить 10⁶ операций (10⁶ ~ 2²⁰) за 1 секунду.

2²⁰ = 1 Second
2⁸⁰ = 37 Billion Years! (Universe is only 13.77 Billion Years Old)

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

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

Давайте попробуем мыслить категориями динамического программирования.

Определение состояний

Определим состояние S [i, j] так, чтобы i было 0≤ i ≤ len (N). а j равно 0 ≤ j ‹K.
Кроме того, пусть Arr [len (N)] быть массивом цифр целого числа N.

Здесь S [i, j] будет true, только если мы сможем добавить несколько цифр из сегмента массива Arr [i, len (N) -1], чтобы оно делилось на K.

Параметр состояния второй, j сохраняет остаток от K для числа до настоящего момента. Ясно, что если мы можем получить этот остаток как 0, это даст нам число, которое делится на K. Это будет наш ответ. Например:

Consider N = 123 and K = 2
Now, state S[0,1] depicts the case where you are on choosing the first digit (index 0) and taking its remainder with 2 (which is 1). You can see its value will be true as you can just include the second digit and the combined number 12 will be divisible by 2. 
Thereforce, S[0,1] will evaluate to true.

Определение переходов

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

Формально переход: S [i, j] → S [i`, j`]

Рассмотрим произвольное состояние S [i, j] из Arr [len (N)].

Теперь вы можете либо удалить текущую цифру Arr [i], либо нет. Таким образом, для каждого индекса массива у вас есть ровно 2 варианта.

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

j` = ((j * 10) + Arr[i]) % K
i` = i + 1

И наоборот, если вы удаляете текущую цифру, вам нужно не выполнять какой-либо такой переход к параметру j, а можно просто перейти к следующему индексу.

j` = j
i` = i + 1

Таким образом, мы можем вернуться к обоим этим состояниям и проверить, из какого перехода мы получаем true (если вообще) в качестве возвращаемого значения.
В зависимости от этого мы можем присвоить значение для текущего укажите для S [i, j] значение истина или ложь.

Получение номера

Теперь нам нужно получить число, которое делилось на K.

Для этого, когда мы продвигаемся к концу цифр, в тот момент, когда мы получаем остаток как 0, мы возвращаем true для всех предыдущих родительских рекурсивных вызовов, которые привели нас в это состояние. Исходя из этого, мы можем просто сохранить цифры, включение которых привело нас к этому истинному состоянию.

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

Код 🎉

Ввод

356652
8

Вывод

3552

Код на C ++ 14

Вуаля! 🌠

Хотите больше подобного контента?

Вы можете связаться со мной в Твиттере здесь: abshekha