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

TOP Interview Coding Problems/Challenges

- Run-length encoding (find/print frequency of letters in a string)
- Sort an array of 0's, 1's and 2's in linear time complexity
- Checking Anagrams (check whether two string is anagrams or not)
- Relative sorting algorithm
- Finding subarray with given sum
- Find the level in a binary tree with given sum K
- Check whether a Binary Tree is BST (Binary Search Tree) or not
- 1[0]1 Pattern Count
- Capitalize first and last letter of each word in a line
- Print vertical sum of a binary tree
- Print Boundary Sum of a Binary Tree
- Reverse a single linked list
- Greedy Strategy to solve major algorithm problems
- Job sequencing problem
- Root to leaf Path Sum
- Exit Point in a Matrix
- Find length of loop in a linked list
- Toppers of Class
- Print All Nodes that don't have Sibling
- Transform to Sum Tree
- Shortest Source to Destination Path

Comments and Discussions

**Ad:**
Are you a blogger? Join our Blogging forum.