Удалите как можно меньше цифр, чтобы число делилось на 3
Я решал этот вопрос, а именно мы дали номер N, который может быть очень большим, он может иметь до 100000 цифр.
Теперь я хочу узнать, как наиболее эффективно найти эти цифры, и я думаю, что в больших числах мне нужно будет удалить не более 3 цифр, чтобы число делилось на 3.
Я знаю, что число делится на три, если сумма его цифр делится на три, но я не могу думать о том, как мы можем использовать это.
Моя идея состоит в том, чтобы перебрать всю строку и проверить, удаляем ли мы эту цифру, это число, которое будет делиться на 3, но мое решение не удается на сложных примерах. Пожалуйста, дайте мне несколько советов.
Заранее спасибо.
4 ответа
Если сумма цифр по модулю 3 равна 1, вы хотите удалить одну цифру 1, 4 или 7. Если сумма цифр равна 2, вы хотите удалить одну цифру 2, 5 или 8.
Если это не может быть сделано, то вы должны удалить две цифры.
Чтобы не сканировать список дважды, вы можете запомнить индексы, содержащие до двух цифр, равных 1, и индексы, содержащие до двух цифр, равные 2, поэтому, когда вы вычисляете окончательный модуль, вы знаете, где искать.
Сумма цифр по модулю 3 равна 1
Deleting 1 digit Option: 1,4,7
Deleting 2 digit Option: 2 5,2 8,5 8,2 2,5 5,8 8
Сумма цифр по модулю 3 равна 2
Deleting 1 digit Option: 2,5,8
Deleting 2 digit Option: 1 4,1 7,4 7,1 1,4 4,7 7
Число 3 имеет некоторые специальные свойства относительно системы счисления с основанием 10, которые вы можете использовать.
10 на 1 больше, чем 9, а 9 делится на 3 равномерно, поэтому "1" в "10" действует как своего рода остаток от добавления 1 к 9. В результате, если сумма всех цифр в числе равна равномерно делится на 3, то это число также делится на 3.
Поэтому, если вы начнете с выяснения, что такое по модулю после добавления всех цифр, то вы будете знать, делится ли число на ноль (то есть приводит ли это к модулю ноль) или нет. Если нет, то вы можете вычитать одну цифру за раз, пересчитывая по модулю полученное число, пока не получите модуль с нулем.
Вы должны проверить, что делает число делимым на 3. Если вы найдете это, вы должны разделить проблему на более мелкие проблемы.