Количество чисел в диапазоне [L, R], сумма цифр квадрата которых равна квадрату суммы цифр

Даны два целых числа L и R, задача состоит в том, чтобы найти количество чисел в диапазоне [L, R] такое, что сумма цифр его квадрата равна квадрату суммы его цифр ,

Пример :

Input: L = 22, R = 22
Output: 1
Explanation: 22 is only valid number in this range as 
sum of digits of its square = S(22*22) = S(484) = 16 and 
square of sum of its digits = S(22)*S(22) = 16

Input: L = 1, R = 58
Output: 12
Explanation: Total valid numbers are {1, 2, 3, 10, 11, 12, 13, 20, 21, 22, 30, 31}

Наивный подход: запустить цикл от L до R и для каждого числа вычислить сумму цифр и проверить, удовлетворяет ли текущее число заданному условию или нет.

Выполните следующие шаги, чтобы решить проблему:

• Итерируйте от L к R и для каждого числа вычислите его сумму цифр.
• Возведите в квадрат текущее число и найдите его сумму цифр.
• Если они равны, увеличьте ответ, в противном случае продолжите для следующего элемента.

Временная сложность: O((RL)*log(R))

Эффективный подход. Из примера 2 видно, что все допустимые числа состоят только из цифр от 0 до 3 . Следовательно, есть только 4 варианта для каждой цифры, присутствующей в числе. Используйте рекурсию, чтобы вычислить все допустимые числа до R и проверить, удовлетворяет ли оно заданному условию или нет.

Выполните следующие шаги, чтобы решить проблему:

• Обратите внимание, что все допустимые числа имеют цифры от [0,3].
• Числа между [4,9] при возведении в квадрат переносятся на них.
  • S(4)*S(4) = 16 и S(16) = 7, 16 != 7.
  • S(5)*S(5) = 25 и S(25) = 7, 25 != 7.
• Итак, сгенерируйте все возможные числа до R .
• Для каждого сгенерированного числа есть всего 4 возможных варианта между [0,3].
• Вычислите все возможные варианты и проверьте условие для каждого из них.

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

Выход:

1

Сложность времени: ( , так как есть 4 варианта для каждой из цифр до длины R , т.е. log10(R) + 1, поэтому временная сложность будет экспоненциальной.

Вспомогательное пространство: (Рекурсивное пространство стека)