Вроде бы все условия выполняются:
[1, 2, 3, 4, 5, 6, 7, 8, 9, 153, 371, 370, 407, 1634, 8208, 9474, 92727, 93084, 54748, 548834, 1741725, 4210818, 9926315, 9800817, 24678051, 24678050, 88593477, 146511208, 912985153, 472335975, 534494836, 4679307774, 32164049651, 94204591914, 32164049650, 82693916578, 40028394225, 42678290603, 44708635679, 49388550606, 28116440335967, 4338281769391371, 4338281769391370, 21897142587612075, 35641594208964132, 35875699062250035, 4498128791164624869, 1517841543307505039, 3289582984443187032, 4929273885928088826]
time: 1679 ms
memory: 6 MB
Найдено чисел: 50
Upd. В коде не было сортировки, при N <= 1 возвращался null, а не пустой массив, некорректно ситал при N = Long.MIN_VALUE.
Ниже исправленный код, валидацию он тоже не проходит
package com.javarush.task.task20.task2025;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
/*
Алгоритмы-числа
*/
public class Solution {
private static long[][] matrix;
private static long[] maxs;
private static long[] mins;
private static ArrayList<Long> resultList = new ArrayList<Long>(); // список с найденными числами
public static long[] getNumbers(long N) {
if (N < 0) return new long[0];
long[] result = null;
int digNumb = getDigNumb(N); // определяем количество цифр в N
matrix = new long[10][digNumb]; // матрица с цифрами, возведенными в степень от 1 до digNumb
maxs = new long[digNumb]; // массив с максимальными значениями для соответствующего разряда
mins = new long[digNumb]; // массив с минимальными значениями для соответствующего разряда
// заполняем matrix, maxs, mins
for (int j = 0; j < digNumb; j++) {
mins[j] = 1*pow(10, j);
maxs[j] = 1*pow(10, j+1) - 1;
for (int i = 0; i < 10; i++) {
matrix[i][j] = pow(i, j + 1);
}
}
maxs[digNumb - 1] = N - 1; // максимальное число, для которого будет осуществлятся поиск (меньше N)
// ищем числа Армстронга для каждого порядка отдельно, начиная с 1
for (int r = 1; r <= digNumb ; r++) {
proc(0, 1, r);
}
// переписываем полученные значения из списка в массив
Collections.sort(resultList);
if (resultList.size() > 0) {
result = new long[resultList.size()];
for (int i = 0; i < resultList.size(); i++) {
result[i] = resultList.get(i);
}
}
else{
result = new long[0];
}
return result;
}
//рекурсивно перебираем все числа. first - наименьшая цифра для текущего разряда;
// digPos - текущий разряд, позиция цифры в числе; numb - число старшего разряда
private static void proc(long numb, int first, int digPos) {
for (int i = first; i < 10; i++) {
long number = i * pow(10, digPos - 1) + numb;
// если текущее число превысило максимальное для Long (стало меньше ноля), выходим
if (number < 0) return;
// если из number путем перестановки его цифр можно получить число Армстронга, находим его
long arm = getArmst(number);
if (arm >= 0 && !resultList.contains(arm))
resultList.add(arm);
if (digPos > 1) proc(number, i, digPos - 1);
}
return;
}
// если сумма цифр числа N, возведенных в степень порядка числа N, является числом Армстронга того же порядка, что
// и N, получаем его, иначе возвращается -1. Если найденное число Армстронга не меньше числа N,
// также возвращается -1
private static long getArmst (long numb) {
long sum = 0;
int digNumb = getDigNumb(numb); // количество цифр в Numb
// считаем sum - сумму всех цифр, возведенных в степень порядка числа
do {
sum += matrix[(int) (numb % 10)][digNumb - 1];
} while ((numb /= 10) > 0);
// если sum больше максимального или минимального числа для данного порядка, возвращаем -1
if(sum > maxs[digNumb - 1] || sum < mins[digNumb - 1]) return -1;
// проверяем, является ли sum числом Армстронга, если да, возвращаем его, если нет, возвращаем -1
long sum1 = 0;
for (long i = sum; i > 0 ; i = i/10) {
sum1 += matrix[(int) (i % 10)][digNumb - 1];
}
if (sum1 != sum) return -1;
return sum;
}
//количество цифр в numb
private static int getDigNumb (long numb) {
long temp = 0L;
int digNumb = 1;
while ((temp = (temp << 3) + (temp << 1) + 9L) < numb && temp > 0)
digNumb++;
return digNumb;
}
// возведение в степень exp числа num
public static long pow (int num, int exp) {
long l = 1;
for (int i = 0; i < exp; i++)
l *= (long)num;
return l;
}
public static void main(String[] args) {
Long t0 = System.currentTimeMillis();
long [] result = getNumbers(Long.MAX_VALUE);
Long t1 = System.currentTimeMillis();
System.out.println(Arrays.toString(result));
System.out.println("time: " + (t1-t0) + " ms");
System.out.println("memory: " + (Runtime.getRuntime().totalMemory() - Runtime.getRuntime().freeMemory())/1000000 + " MB");
System.out.println("Найдено чисел: " + result.length);
}
}
package com.javarush.task.task20.task2025;
import java.util.ArrayList;
import java.util.Arrays;
/*
Алгоритмы-числа
*/
public class Solution {
private static long[][] matrix;
private static long[] maxs;
private static long[] mins;
private static ArrayList<Long> resultList = new ArrayList<Long>(); // список с найденными числами
public static long[] getNumbers(long N) {
long[] result = null;
int digNumb = getDigNumb(N); // определяем количество цифр в N
matrix = new long[10][digNumb]; // матрица с цифрами, возведенными в степень от 1 до digNumb
maxs = new long[digNumb]; // массив с максимальными значениями для соответствующего разряда
mins = new long[digNumb]; // массив с минимальными значениями для соответствующего разряда
// заполняем matrix, maxs, mins
for (int j = 0; j < digNumb; j++) {
mins[j] = 1*pow(10, j);
maxs[j] = 1*pow(10, j+1) - 1;
for (int i = 0; i < 10; i++) {
matrix[i][j] = pow(i, j + 1);
}
}
maxs[digNumb - 1] = N - 1; // максимальное число, для которого будет осуществлятся поиск (меньше N)
// ищем числа Армстронга для каждого порядка отдельно, начиная с 1
for (int r = 1; r <= digNumb ; r++) {
proc(0, 1, r);
}
// переписываем полученные значения из списка в массив
if (resultList.size() > 0) {
result = new long[resultList.size()];
for (int i = 0; i < resultList.size(); i++) {
result[i] = resultList.get(i);
}
}
return result;
}
//рекурсивно перебираем все числа. first - наименьшая цифра для текущего разряда;
// digPos - текущий разряд, позиция цифры в числе; numb - число старшего разряда
private static void proc(long numb, int first, int digPos) {
for (int i = first; i < 10; i++) {
long number = i * pow(10, digPos - 1) + numb;
// если текущее число превысило максимальное для Long (стало меньше ноля), выходим
if (number < 0) return;
// если из number путем перестановки его цифр можно получить число Армстронга, находим его
long arm = getArmst(number);
if (arm >= 0 && !resultList.contains(arm))
resultList.add(arm);
if (digPos > 1) proc(number, i, digPos - 1);
}
return;
}
// если сумма цифр числа N, возведенных в степень порядка числа N, является числом Армстронга того же порядка, что
// и N, получаем его, иначе возвращается -1. Если найденное число Армстронга не меньше числа N,
// также возвращается -1
private static long getArmst (long numb) {
long sum = 0;
int digNumb = getDigNumb(numb); // количество цифр в Numb
// считаем sum - сумму всех цифр, возведенных в степень порядка числа
do {
sum += matrix[(int) (numb % 10)][digNumb - 1];
} while ((numb /= 10) > 0);
// если sum больше максимального или минимального числа для данного порядка, возвращаем -1
if(sum > maxs[digNumb - 1] || sum < mins[digNumb - 1] || sum < 0) return -1;
// проверяем, является ли sum числом Армстронга, если да, возвращаем его, если нет, возвращаем -1
long sum1 = 0;
for (long i = sum; i > 0 ; i = i/10) {
sum1 += matrix[(int) (i % 10)][digNumb - 1];
}
if (sum1 != sum) return -1;
return sum;
}
//количество цифр в numb
private static int getDigNumb (long numb) {
long temp = 0L;
int digNumb = 1;
while ((temp = (temp << 3) + (temp << 1) + 9L) < numb && temp > 0)
digNumb++;
return digNumb;
}
// возведение в степень exp числа num
public static long pow (int num, int exp) {
long l = 1;
for (int i = 0; i < exp; i++)
l *= (long)num;
return l;
}
public static void main(String[] args) {
Long t0 = System.currentTimeMillis();
long [] result = getNumbers(Long.MAX_VALUE);
System.out.println(Arrays.toString(result));
Long t1 = System.currentTimeMillis();
System.out.println("time: " + (t1-t0) + " ms");
System.out.println("memory: " + (Runtime.getRuntime().totalMemory() - Runtime.getRuntime().freeMemory())/1000000 + " MB");
System.out.println("Найдено чисел: " + result.length);
}
}