Количество различных чисел, делящихся на 3, которые можно получить, заменив не более одной цифры

Дана строка str , представляющая число имеющий N цифр, задача состоит в том, чтобы посчитать, сколько способов разделить заданное число на 3, заменив не более одной цифры числа.

Примеры:

Input: str[] = “23”
Output: 7
Explanation: Below are the numbers that can be made from the string which are divisible by 3 – 03, 21, 24, 27, 33, 63, 93
1.Change 2 to 0 (0+3)=3 divisible by 3
2.Change 3 to 1 (2+1)=3 divisible by 3
3 change 3 to 4 (2+4)=6 divisible by 3
4 change 2 to 3 sum is 6 divisible by 3
Similarly there are total 7 number of ways to make the given number divisible by 3

Input: str[] = “235”
Output: 9

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

• Инициализируйте переменную sum как 0 , чтобы сохранить сумму цифр числа.
• Переберите диапазон [0, N], используя переменную i , и выполните следующие шаги:
  • Добавьте значение цифры по i-му индексу в переменную sum.
• Инициализируйте переменную count как 0 , чтобы сохранить ответ.
• Если само число делится на 3, то увеличивайте счетчик на единицу.
• Переберите диапазон [0, N], используя переменную i , и выполните следующие шаги:
  • Инициализируйте переменную rest_sum как sum-(number.charAt(i)-48).
  • Переберите диапазон [0, 9], используя переменную j , и выполните следующие шаги:
    • Прибавляем значение j к переменной оставшаяся_сумма и если оставшаяся_сумма делится на 3 и j не равно цифре в i-м индексе, то прибавляем значение count на 1.
• После выполнения вышеуказанных шагов выведите значение count в качестве ответа.

Ниже приведена реализация вышеуказанного подхода.

Временная сложность: O(N)
Вспомогательное пространство: O(1)