Un número mágico se define como un número que se puede expresar como una potencia de 5 o la suma de potencias únicas de 5. Los primeros números mágicos son 5, 25, 30 (5 + 25), 125, 130 (125 + 5), ….
Escribe una función para encontrar el enésimo número mágico.
Ejemplo:
Input: n = 2 Output: 25 Input: n = 5 Output: 130
Si nos fijamos bien, los números mágicos se pueden representar como 001, 010, 011, 100, 101, 110, etc., donde 001 es 0*pow(5,3) + 0*pow(5,2) + 1*pow(5 ,1). Entonces, básicamente, necesitamos sumar potencias de 5 para cada bit establecido en un entero n dado.
A continuación se muestra la implementación basada en esta idea.
Acercarse :
Paso 1: declara y asigna un número para el que quieres encontrar el número mágico.
Paso 2: asigne un pow = 1 y ans = 0
Paso 3: usa el ciclo while para iterar cada bit hasta el final (mientras que n > 0)
Paso 4: bucle interno, encuentre el último bit de uso y operación y siga actualizando la respuesta y la potencia también
Paso 5: una vez que salga del bucle, devuelva la respuesta
C++
// C++ program to find nth magic number #include <bits/stdc++.h> using namespace std; // Function to find nth magic number int nthMagicNo(int n) { int pow = 1, answer = 0; // Go through every bit of n while (n) { pow = pow*5; // If last bit of n is set if (n & 1) answer += pow; // proceed to next bit n >>= 1; // or n = n/2 } return answer; } // Driver program to test above function int main() { int n = 5; cout << "nth magic number is " << nthMagicNo(n) << endl; return 0; }
Java
// Java program to find nth // magic number import java.io.*; class GFG { // Function to find nth magic number static int nthMagicNo(int n) { int pow = 1, answer = 0; // Go through every bit of n while (n != 0) { pow = pow*5; // If last bit of n is set if ((int)(n & 1) == 1) answer += pow; // proceed to next bit // or n = n/2 n >>= 1; } return answer; } // Driver program to test // above function public static void main(String[] args) { int n = 5; System.out.println("nth magic" + " number is " + nthMagicNo(n)); } } // This code is contributed by // prerna saini
Python3
# Python program to find nth magic number # Function to find nth magic number def nthMagicNo(n): pow = 1 answer = 0 # Go through every bit of n while (n): pow = pow*5 # If last bit of n is set if (n & 1): answer += pow # proceed to next bit n >>= 1 # or n = n/2 return answer # Driver program to test above function n = 5 print("nth magic number is", nthMagicNo(n)) # This code is contributed by # Smitha Dinesh Semwal
C#
// C# program to find nth // magic number using System; public class GFG { // Function to find nth magic number static int nthMagicNo(int n) { int pow = 1, answer = 0; // Go through every bit of n while (n != 0) { pow = pow * 5; // If last bit of n is set if ((int)(n & 1) == 1) answer += pow; // proceed to next bit // or n = n/2 n >>= 1; } return answer; } // Driver Code public static void Main() { int n = 5; Console.WriteLine("nth magic" + " number is " + nthMagicNo(n)); } } // This code is contributed by Sam007
PHP
<?php // PHP program to find nth // magic number // Function to find nth // magic number function nthMagicNo($n) { $pow = 1; $answer = 0; // Go through every bit of n while ($n) { $pow = $pow * 5; // If last bit of n is set if ($n & 1) $answer += $pow; // proceed to next bit $n >>= 1; // or $n = $n/2 } return $answer; } // Driver Code $n = 5; echo "nth magic number is ", nthMagicNo($n), "\n"; // This code is contributed by Ajit. ?>
Javascript
<script> // Javascript program to find nth // magic number // Function to find nth magic number function nthMagicNo(n) { let pow = 1, answer = 0; // Go through every bit of n while (n != 0) { pow = pow * 5; // If last bit of n is set if ((n & 1) == 1) answer += pow; // proceed to next bit // or n = n/2 n >>= 1; } return answer; } let n = 5; document.write("nth magic" + " number is " + nthMagicNo(n)); </script>
Producción :
nth magic number is 130
Complejidad :
Complejidad de tiempo : O (logN)
Espacio Auxiliar : O(1)
Gracias a manrajsingh por sugerir la solución anterior.
Este artículo es una contribución de Abhay . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA