Весь набор чисел Армстронга для long получаю, в лимиты по времени и памяти укладываюсь.
Возвращает наборы < N, сортированные по возрастанию.
Для всех входных параметров <= 0 отдает пустой массив. Для 1 - тоже (поскольку строго меньше N).
Блин, что не так-то?
Вот вывод для Long.MAX_VALUE:
[1, 2, 3, 4, 5, 6, 7, 8, 9, 153, 370, 371, 407, 1634, 8208, 9474, 54748, 92727, 93084, 548834, 1741725, 4210818, 9800817, 9926315, 24678050, 24678051, 88593477, 146511208, 472335975, 534494836, 912985153, 4679307774, 32164049650, 32164049651, 40028394225, 42678290603, 44708635679, 49388550606, 82693916578, 94204591914, 28116440335967, 4338281769391370, 4338281769391371, 21897142587612075, 35641594208964132, 35875699062250035, 1517841543307505039, 3289582984443187032, 4498128791164624869, 4929273885928088826]
Used memory: 12.798MB
Elapsed time = 3,846ms
package com.javarush.task.task20.task2025;
import java.util.*;
/*
Алгоритмы-числа
*/
public class Solution {
public static long[][] powMatrix; // Таблица степеней
public static Map<Long, Boolean> amap = new TreeMap<>();
public static int[] arrDig;
public static long curN;
static { // вычисляем таблицу степеней
int maxD = (int) ("" + Long.MAX_VALUE).length();
powMatrix = new long[10][maxD + 1];
powMatrix[0][0] = 0l;
long l;
for(int i = 0; i < 10; i++) {
for(int j = 0; j <= maxD; j++) {
if(i == 0) powMatrix[i][j] = 0l;
else {
powMatrix[i][j] = 1l;
for (int k = 0; k < j; k++) {
powMatrix[i][j] *= i;
}
}
}
}
}
public static long[] getNumbers(long N) {
long[] result;
if(N < 1) return new long[0];
curN = N;
// Массив хранения цифр всех перебираемых чисел нашей размерности
int d = (int) ("" + N).length();
arrDig = new int[d];
// инициализируем массив цифр
for(int i = 0; i < d; i++) {
arrDig[i] = 0;
}
// Перебор уникальных наборов цифр
while (arrDig[0] < 9) {
getNext(); // следующий набор в массиве arrDig
checkArmstrong(0);
// цикл проверок на ведущие нули
for(int i = 0; i < arrDig.length; i++) {
if(arrDig[i] != 0) break;
checkArmstrong(i + 1);
}
// end of цикл проверок на ведущие нули
}
result = new long[amap.size()];
int i = 0;
for(Map.Entry<Long, Boolean> l: amap.entrySet()) {
if(l.getKey() >= N) break;
result[i] = l.getKey();
i++;
}
return result;
}
static void checkArmstrong(int start) {
// Вычислим сумму Армстронга в массиве
int dim = arrDig.length - start;
long sumArm = 0l;
for(int i = start; i < arrDig.length; i++) {
sumArm += powMatrix[arrDig[i]][dim];
if(sumArm < 0) return; // выход за пределы размерности long
}
// Проверяем полученную сумму на сумму Армстронга
byte[] bytes = ("" + sumArm).getBytes();
int dimSum = bytes.length;
if(dim != dimSum) return;
long sumArmSum = 0l;
for(int i = 0; i < dimSum; i++) {
int r = Character.getNumericValue(bytes[i]);
try {
sumArmSum += powMatrix[r][dimSum];
}
catch (ArrayIndexOutOfBoundsException ex) {
sumArmSum = -1;
break;
}
}
if((sumArmSum == sumArm) && (sumArm < curN)) amap.put(sumArm, true);
}
static void getNext() {
// получим следующий набор в массиве arrDig
int i, j;
for(i = arrDig.length - 1; i >= 0; i--) { // начинаем с младшего разряда
if(arrDig[i] < 9) {
arrDig[i]++; // инкрементировали текущий разряд
// выравниваем по нему все разряды младше текущего
for (j = i + 1; j < arrDig.length; j++) {
arrDig[j] = arrDig[i];
}
// здесь инкрементированный новый набор
return;
}
}
}
public static void main(String[] args) {
long a = System.currentTimeMillis();
System.out.println(Arrays.toString(getNumbers(Long.MAX_VALUE)));
long b = System.currentTimeMillis();
// System.out.println("memory " + (Runtime.getRuntime().totalMemory() - Runtime.getRuntime().freeMemory()) / (8 * 1024));
// System.out.println("time = " + (b - a) / 1000);
long used_memory = Runtime.getRuntime().totalMemory() - Runtime.getRuntime().freeMemory();
long full_time = b - a;
System.out.printf("Used memory: %.3fMB\n", 1f * used_memory / (1024 * 1024));
System.out.printf("Elapsed time = %,dms\n", full_time);
}
}