# Find nth Magic Number

A magic number is defined as a number which can be expressed as a power of 5 or sum of unique powers of 5. First few magic numbers are 5, 25, 30(5 + 25), 125, 130(125 + 5), ….

Write a function to find the nth Magic number.

Example:

```Input: n = 2
Output: 25

Input: n = 5
Output: 130 ```

If we notice carefully the magic numbers can be represented as 001, 010, 011, 100, 101, 110 etc, where 001 is 0*pow(5,3) + 0*pow(5,2) + 1*pow(5,1). So basically we need to add powers of 5 for each bit set in given integer n.

Below is the implementation based on this idea.

## C++

 `// C++ program to find nth magic numebr ` `#include ` `using` `namespace` `std; ` ` `  `// Function to find nth magic numebr ` `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 numebr ` `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 numebr ` ` `  `# Function to find nth magic numebr ` `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 numebr ` `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

 `>= 1; ``// or \$n = \$n/2 ` `    ``} ` `    ``return` `\$answer``; ` `} ` ` `  `// Driver Code ` `\$n` `= 5; ` `echo` `"nth magic number is "``,  ` `       ``nthMagicNo(``\$n``), ````" "````; ` ` `  `// This code is contributed by Ajit. ` `?> `

Output :

` nth magic number is 130 `

Thanks to manrajsingh for suggesting above solution.