Dados dos enteros A y N , la tarea es calcular A elevado a N (es decir, A N ).
Ejemplos:
Entrada: A = 3, N = 5
Salida: 243
Explicación:
3 elevado a la potencia 5 = (3*3*3*3*3) = 243Entrada: A = 21, N = 4
Salida: 194481
Explicación:
21 elevado a la potencia 4 = (21*21*21*21) = 194481
Enfoque ingenuo:
el enfoque más simple para resolver este problema es multiplicar repetidamente A , N veces e imprimir el producto.
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Enfoque eficiente:
para optimizar el enfoque anterior, la idea es utilizar la manipulación de bits . Convierta el número entero N a su forma binaria y siga los pasos a continuación:
- Inicialice ans para almacenar la respuesta final de A N .
- Atraviese hasta N > 0 y en cada iteración, realice la operación de desplazamiento a la derecha en él.
- Además, en cada iteración, multiplica A consigo mismo y actualízalo.
- Si se establece el LSB actual , multiplique el valor actual de A por ans .
- Finalmente, después de completar los pasos anteriores, imprima ans .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ Program to implement // the above approach #include <iostream> using namespace std; // Function to return a^n int powerOptimised(int a, int n) { // Stores final answer int ans = 1; while (n > 0) { int last_bit = (n & 1); // Check if current LSB // is set if (last_bit) { ans = ans * a; } a = a * a; // Right shift n = n >> 1; } return ans; } // Driver Code int main() { int a = 3, n = 5; cout << powerOptimised(a, n); return 0; }
Java
// Java program to implement // the above approach class GFG{ // Function to return a^n static int powerOptimised(int a, int n) { // Stores final answer int ans = 1; while (n > 0) { int last_bit = (n & 1); // Check if current LSB // is set if (last_bit > 0) { ans = ans * a; } a = a * a; // Right shift n = n >> 1; } return ans; } // Driver Code public static void main(String[] args) { int a = 3, n = 5; System.out.print(powerOptimised(a, n)); } } // This code is contributed by PrinciRaj1992
Python3
# Python3 program to implement # the above approach # Function to return a^n def powerOptimised(a, n): # Stores final answer ans = 1 while (n > 0): last_bit = (n & 1) # Check if current LSB # is set if (last_bit): ans = ans * a a = a * a # Right shift n = n >> 1 return ans # Driver code if __name__ == '__main__': a = 3 n = 5 print(powerOptimised(a,n)) # This code is contributed by virusbuddah_
C#
// C# program to implement // the above approach using System; class GFG{ // Function to return a^n static int powerOptimised(int a, int n) { // Stores readonly answer int ans = 1; while (n > 0) { int last_bit = (n & 1); // Check if current LSB // is set if (last_bit > 0) { ans = ans * a; } a = a * a; // Right shift n = n >> 1; } return ans; } // Driver Code public static void Main(String[] args) { int a = 3, n = 5; Console.Write(powerOptimised(a, n)); } } // This code is contributed by Princi Singh
Javascript
<script> // Javascript program to implement // the above approach // Function to return a^n function powerOptimised(a, n) { // Stores final answer let ans = 1; while (n > 0) { let last_bit = (n & 1); // Check if current LSB // is set if (last_bit > 0) { ans = ans * a; } a = a * a; // Right shift n = n >> 1; } return ans; } // Driver Code let a = 3, n = 5; document.write(powerOptimised(a, n)); </script>
243
Complejidad temporal: O(logN)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por theamanamanaman y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA