Не знаю, как ускорить алгоритм.
package com.javarush.task.task20.task2025;
/*
Алгоритмы-числа
*/
/*
Число S состоит из M цифр, например, S=370 и M (количество цифр) = 3
Реализовать логику метода getNumbers, который должен среди натуральных чисел меньше N (long)
находить все числа, удовлетворяющие следующему критерию:
число S равно сумме его цифр, возведенных в M степень
getNumbers должен возвращать все такие числа в порядке возрастания.
*/
import java.util.Collections;
import java.util.TreeSet;
public class Solution {
public static long[] getNumbers(long N) {
long[] result = null;
TreeSet<Integer> set = new TreeSet<>();
//Заполняем массив со степенями цифр
long[][] degree = new long[9][String.valueOf(Long.MAX_VALUE).length()];
for (int i = 0; i < 9; i++) {
double number = i + 1;
for (int j = 0; j < String.valueOf(Long.MAX_VALUE).length(); j++) {
double power = j + 1;
degree[i][j] = (long) Math.pow(number, power);
}
}
for (long i = 1; i <= N; i++) {
int S = (int) i;
char[] numbers = String.valueOf(Math.abs(S)).toCharArray();
//Проверяем, есть ли смысл рассматривать это число
boolean checkThisNumber = true;
for (int j = 0; j < numbers.length - 1; j++) {
if (Integer.parseInt("" + numbers[j]) > Integer.parseInt("" + numbers[j + 1])) {
checkThisNumber = false;
break;
}
}
if (checkThisNumber) {
int M = numbers.length;
long amount = 0;
for (char number : numbers
) {
int n = Integer.parseInt("" + number);
//берём степеь из массива
long stepen = degree[n - 1][M - 1];
amount = amount + stepen;
}
if (S == amount) {
set.add(S);
}
}
}
result = new long[set.size()];
int i = 0;
for (Integer number : set
) {
result[i] = (long) number;
i++;
}
return result;
}
public static void main(String[] args) {
long[] numbers = getNumbers(Integer.MAX_VALUE);
for (long n : numbers
) {
System.out.println(n);
}
}
}