Tutorialspoint.dev

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 <bits/stdc++.h>
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

<?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), " ";
  
// This code is contributed by Ajit.
?>

Output :

 nth magic number is 130 

Thanks to manrajsingh for suggesting above solution.



This article is attributed to GeeksforGeeks.org

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter