# Find nth Magic number

In this article, we are going to see a sequence of numbers and finding the generating algorithm. This problem has been featured in Amazon.
Submitted by Radib Kar, on April 04, 2019

Problem statement:

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).

Given the value of n, find the nth Magic number.

Example:

```    Input:
N=1
Output: 5

Input:
N=2
Output :25

Input:
N=3
Output: 30
```

Solution:

One naïve approach is to use a set to store the sequence of magic numbers. We store the powers of 5, and then try all combination sum between the unique powers and insert the sums into the set if it already not there. Set sorts the insertion and so as the set size reaches to N, we can output the last number in the set/ largest no in the set.

Find finding sums between different combinations are tedious and N-P hard problem if solved in general.

So the solution is something different.

Let's manually compute the magic numbers first and try to observe the generated sequence as a whole.

```    First one is obviously 5

Next would be 25

Now we can find a combination sum and that’s only one, 25+5=30
No other combinations possible till now.
(Don't thing 30+5=35 a magic number, we can some only unique powers of 5)

Next will be 125

Then we have few combinations like
5+125=130
25+125=150
5+25+125=155

No more combinations possible up to now

Next would be 625

Then we have few combinations like

5+625=630
25+625=650
5+25+625=655
125+625=750
5+125+625=755
25+125+625=775
5+25+125+625=780

No more combinations possible up to now

Next will be 5^4=3125

And few more combinations so on

So, sequence is:
5 25 30 125 130 150 155 625 630 650 655 750 755 775 780 3125 ...

This is actually similar pattern like binary numbers
0001
0010
0011
0100
0101
0110
0111
1000
-----------------------------------------------------

But here the base is not 2

The base is pow(5, i) where i is indexed-1 the bit position counted from LSB

So, 0001 =0*pow(5,4)+0*pow(5,3)+0*pow(5,2) +1*pow(5,1)=5

Rest of the sequence can be calculated so on

Say, We need to find N th magic number.

We have binary representation of N

What we need to do is to convert the base to number to base pow(5,i) number

Note: This may seem to be same as converting to base 5 number,
but this is not. For base 5 number I would have start from 0 for LSB
That's not a big deal.

# define max 10^9+7
(modulo max is done as answer can be too big to be hold even by long long)
```

Algo:

```    1.  Declare pro=1;
3.  While(n is not 0)
pro=(pro*5)%max; //pow(5,i)
IF (n&1) //current LSB is 1
END IF
n=n>>1; //right shift n, similar to diving by 2
End While
```

C++ implementation:

```#include <bits/stdc++.h>
using namespace std;
#define max 1000000007

long long int magicNo(int n){
long long int pro=1;
while(n){
pro=(pro*5)%max; //pow(5,i)
if(n&1) //current LSB 1
n=n>>1; //right shift by 1 bit
}
}

int main()
{
int n;

cout<<"Enter N:\n";
scanf("%d",&n);
cout<<n<<" th magic no is: ";
cout<<magicNo(n)<<endl;

return 0;
}
```

Output

```Enter N:
5
5 th magic no is: 130
```

Languages: » C » C++ » C++ STL » Java » Data Structure » C#.Net » Android » Kotlin » SQL
Web Technologies: » PHP » Python » JavaScript » CSS » Ajax » Node.js » Web programming/HTML
Solved programs: » C » C++ » DS » Java » C#
Aptitude que. & ans.: » C » C++ » Java » DBMS
Interview que. & ans.: » C » Embedded C » Java » SEO » HR
CS Subjects: » CS Basics » O.S. » Networks » DBMS » Embedded Systems » Cloud Computing
» Machine learning » CS Organizations » Linux » DOS
More: » Articles » Puzzles » News/Updates