Home » Interview coding problems/challenges

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;
    2.  Declare  answer=0;
    3.  While(n is not 0)
            pro=(pro*5)%max; //pow(5,i)
            IF (n&1) //current LSB is 1
                answer=(answer + pro)%max;
            END IF
            n=n>>1; //right shift n, similar to diving by 2
        End While
    4.	return answer;

C++ implementation:

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

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

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