Найдите значение числа, возведенного в обратную сторону

Даны число N и его реверс R. Задача состоит в том, чтобы найти число, полученное при возведении числа в степень его реверса. Ответ может быть очень большим, верните результат по модулю 10 ⁹ +7.

Примеры:

 Input : N = 2, R = 2
Output: 4
Explanation: Number 2 raised to the power of its reverse 2 gives 4 which gives 4 as a result after performing modulo 10⁹+7

Input : N = 57, R = 75
Output: 262042770
Explanation: 57⁷⁵ modulo 10⁹+7 gives us the result as 262042770

Наивный подход:

The easiest way to solve this problem could be to traverse a loop from 1 to R(reverse) and multiply our answer with N  in each iteration.

Следуйте шагам, указанным ниже, чтобы реализовать идею:

• Создайте переменную (например, an ) и инициализируйте ее значением 1 , чтобы сохранить окончательный результат.
• Затем начните цикл с 1 , и он идет до R .
  • Умножьте переменную ans на N.
• Возвратите результат по модулю 1e9+7 .

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

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

Эффективный подход: битовые манипуляции

The efficient way of solving this problem could be bit manipulation, just break the problem into small parts and solve them here the concept of binary exponentiation method will be used.

• Every number can be written as the sum of powers of 2
• Traverse through all the bits of a number from LSB (Least Significant Bit) to MSB (Most Significant Bit) in O(log N) time.

Следуйте шагам, указанным ниже, чтобы реализовать идею:

• Сначала создайте переменную (например, ans ) и инициализируйте ее значением 1, чтобы сохранить результат.
• Затем проверьте, является ли данное обратное число нечетным или нет.
  • Если да, то умножьте ответ на pow ans = (ans * pow)%mod .
  • Затем умножьте pow на pow , т.е. pow = (pow*pow).
  • Начните сдвиг вправо на R = R/2 .
• Наконец, верните ответ как результат.

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

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