Find Nth Magic Number

Problem: Given a number n, find out the nth Magic Number.

Magic Numbers: 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), ...

For example:

Input: n = 25
Output: 3755

Input: n = 30
Output: 3900

Analysing the numbers, we observe that 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.

public class MagicNumber {

    /* function returning nth Magic Number */
    public static int NthMagicNum(int n) {
        
        int pow = 1, ans = 0;
        
        /* traversing every bit of n */
        while (n > 0)
        {
           pow = pow*5;
     
           /* If last bit of n is set */
           if ((n & 1) == 1)
             ans += pow;
     
           /* proceed to next bit */
           n >>= 1;
        }
        return ans;
    }
    
    public static void main(String[] args) {
        int n = 120;
        System.out.println(NthMagicNum(n));
    }
}

Output:

97500