Find all narcissistic (armstrong) numbers faster on Java

Question

Is there more efficient way to do that? Given number N - find all the narcissistic ( armstrong ) numbers that < N. Here is my code, but I guess there is more efficient solutions. Also, probably, we could solve it through bit operation?

public static void main(String args[]) throws  Exception
 {
    long a = System.nanoTime();
    int t [] = getNumbers(4_483_647L);
    long b = System.nanoTime();
    System.out.println("Time totally "+(b-a));
    for(int k: t)
        System.out.print(k+" ");
}
public static int[] getNumbers(long N)
{

    int length=1;
    int porog=10, r=1, s=1;
    double k;
    LinkedList<Integer> list = new LinkedList<>();

    for(int i=1; i<N; i++)
    {
        if(i==porog)
        {
            length++;
            porog*=10;
        }
        s = i;
        k=0;
        while(s>0)
        {
            r = s%10;
            k+=Math.pow(r, length);
            if(k>i)break;
            s=s/10;
        }
        if((int)k==i)
            list.add(i);
    }
   int[] result  = new int[list.size()];
    int i=0;
    for(int n: list)
    {
        result[i] = n;
        i++;
    }

    return result;  }  }

Answer 1

A major optimisation is to not examine all the numbers in range 1..N . Have a look here.

Answer 2

I'm not a professional coder, just self taught with no work experience, so I apologize if my code is bit sloppy.

I took dovetalk's solution and 1) wrote it myself so to better understand it b) made some adjustments that improved the run time considerably for large numbers. I hope this helps anyone else looking for help with this problem:

 public static long[] getNumbers(long N) {

        long tempII = N;
        LinkedHashSet<Long> narcNums = new LinkedHashSet<>();

        long tempResult;
        long digitLengthTemp = 10;
        long tempI;
        long[] powers = {0l, 1l, 2l, 3l, 4l, 5l, 6l, 7l, 8l, 9l};

        for (long i = 0; i < N; i++) {
            if (i == digitLengthTemp) {
                digitLengthTemp *= 10;
                for (short x = 2; x < powers.length; x++) powers[x] *= x;
            }
            //set value of top digits of numbers past first 3 to a remedial value
            tempI = i;
            long remedialValue = 0;
            tempI /= 10; tempI /= 10; tempI /= 10;

            while (tempI > 0) {
                short index = (short) (tempI % 10);
                remedialValue += powers[index];
                tempI /= 10;
            }
            //only passes 1000 at a time to this loop and adds each result to remedial top half
            for (int j = 0; j < (tempII > 1000 ? 1000 : tempII); j++) {
                //sets digit length and increases the values in array
                if (i == 0 && j == digitLengthTemp) {
                    digitLengthTemp *= 10;
                    for (short x = 2; x < powers.length; x++) powers[x] *= x;

                }
                //resets temp results
                tempResult = remedialValue;
                tempI = j;


                //gets the sum of each (digit^numberLength) of number passed to it
                while (tempI > 0) {
                    if (tempResult > i + j) break;
                    short index = (short) (tempI % 10);
                    tempResult += powers[index];
                    tempI /= 10;
                }

                //checks if sum equals original number
                if (i + j == tempResult) narcNums.add(i + j);
            }
            i += 999; // adds to i in increments of 1000
            tempII -= 1000;
        }

        //converts to long array
        long[] results = new long[narcNums.size()];
        short i = 0;
        for (long x : narcNums) {
            results[i++] = x;
        }
        return results;
}

Answer 3

It's possible to generate Armstrong Numbers quite efficient. For example, all integers can be generated within 10-15 ms.

We may note that for each multi-set of digits, like [1, 1, 2, 4, 5, 7, 7] there is only one sum of powers, which in its turn may either be or be not represented by the digits from set. In the example 1^7 + 1^7 + 2^7 + 4^7 + 5^7 + 7^7 + 7^7 = 1741725, which can be represented by the digits and thus is an Armstrong number.

We may build an algorithm basing on this consideration.

1. For each number length from 1 to N
2. Generate all possible multi-sets of N digits
3. For each multi-set calculate sum of digits^N
4. Check if it's possible to represent the number we got on step 4 with the digits from the multi-set
5. If so - add the number to the result list

The number of cases calculated for each length N is equal to the number of combinations (N + 9, 9) = (N+9)!/(9!N!). Thus for all Ns less than 10 we will generate only 92,377 multi-sets. For N<20: 20,030,009.

Please see GitHub for the description of a few approaches, along with some benchmarking and the Java code. Enjoy! :)

Answer 4

Some observations:

• If your initial maximum is a long, your results should be long types, too, just in case (int works for you as the narcissistic numbers are far apart)
• If you change your return type to be a "big" Long, you can use Collections.toArray() to repack the results to an array...
• ...although really, you should just return the linked list...
• You don't need to keep recalculating powers. For each decade in the outer loop, you only ever need i^j, where i=0..9 and j is the number of digits in the current decade
• In fact, you don't need Math.pow() at all, as you can just use multiplication at each decade

Applying my ideas from my comment above and also changing the method signature, you get something that runs about 30 times faster:

public static Long[] getNumbers(long N) {
    int porog = 10;
    LinkedList<Long> list = new LinkedList<>();
    // initial powers for the number 0-9
    long[] powers = { 0l, 1l, 2l, 3l, 4l, 5l, 6l, 7l, 8l, 9l };

    for (long i = 1; i < N; i++) {
        if (i == porog) {
            porog *= 10;
            // calculate i^length
            for (int pi = 1; pi < 10; pi++) {
                powers[pi] *= pi;
            }
        }
        long s = i;
        long k = 0;
        while (s > 0) {
            int r = (int)(s % 10);
            k += powers[r];
            if (k > i)
                break;
            s /= 10;
        }

        if (k == i)
            list.add(i);
    }

    return list.toArray(new Long[]{});
}

Answer 5

From Rosetta Code blog (not my own code)

public static boolean isNarc(long x){
    if(x < 0) return false;

    String xStr = Long.toString(x);
    int m = xStr.length();
    long sum = 0;

    for(char c : xStr.toCharArray()){
        sum += Math.pow(Character.digit(c, 10), m);
    }
    return sum == x;
}