Narcissistic Number(lintcode 147)

Description

Narcissistic Number is a number that is the sum of its own digits each raised to the power of the number of digits. See wiki

For example the 3-digit decimal number 153 is a narcissistic number because $$153 = 1^3 + 5^3 + 3^3$$.

And the 4-digit decimal number 1634 is a narcissistic number because $$1634 = 1^4 + 6^4 + 3^4 + 4^4$$.

Given n, return all narcissistic numbers with n digits.

Notice:
You may assume n is smaller than 8.

Example

Given 1, return [0,1,2,3,4,5,6,7,8,9].

Given 2, return [].

Interface

class Solution {
    /*
     * @param n: The number of digits. 
     * @return: All narcissistic numbers with n digits.
     */
    public ArrayList<Integer> getNarcissisticNumbers(int n) {
        // write your code here
    }
};

Idea

Write the code according to the definition of Narcissistic Number. Numbers with only one digit have to be considered separately because zero is also a Narcissistic Number.

Solution

class Solution {
    /*
     * @param n: The number of digits. 
     * @return: All narcissistic numbers with n digits.
     */
    public ArrayList<Integer> getNarcissisticNumbers(int n) {
        // write your code here
        int lower = 1, upper;
        for (int i = 0; i < n - 1; ++i) {
            lower *= 10;
        }

        upper = lower * 10 - 1;

        if (n == 1) {
            lower = 0;
        }

        ArrayList<Integer> res = new ArrayList<Integer>();
        for (int i = lower; i <= upper; ++i) {
            int temp = i;
            int sum = 0;
            while (temp != 0) {
                sum += Math.pow(temp % 10, n);
                temp /= 10;
            }

            if (sum == i) {
                res.add(i);
            }
        }

        return res;
    }
};