мой вариант
[1, 2, 3, 4, 5, 6, 7, 8, 9, 153, 370, 371, 407]
memory : 1.280 Mb
time : 0.001 s
[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]
memory : 2.560 Mb
time : 0.006 s
"правильное решение"
[1, 2, 3, 4, 5, 6, 7, 8, 9, 153, 370, 371, 407]
memory 1310
time = 0
[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]
memory 1966
time = 0package com.javarush.task.task20.task2025;
import java.util.*;
/*
Алгоритмы-числа
*/
public class Solution {
private static long[][] pows = new long[10][20];
private static int N;
private static long maxPow;
private static long minPow;
private static int[] digitMultiSet = new int[10];
private static Set<Long> results = new TreeSet<>();
public static long[] getNumbers(long limit) {
if (limit <= 1) return new long[0];
for (int i = 0; i < pows.length; i++) {
for (int j = 0; j < pows[i].length; j++) {
pows[i][j] = (long) Math.pow(i, j);
}
}
// fast :)
for (N = 1; N <= String.valueOf(limit).length(); N++) {
minPow = (long) Math.pow(10, N - 1);
maxPow = (long) Math.pow(10, N);
search(0, N, 0);
}
N = 0;
long[] result = new long[results.size()];
for (Long a: results) {
if (a < limit) {
result[N] = a;
N++;
} else {
break;
}
}
/* slow :(
N = 0;
long[] result = new long[88];
for (long i = 1; i < limit; i++) {
if (isArmstrong(i)) {
result[N] = i;
N++;
}
}
*/
result = Arrays.copyOfRange(result, 0, N);
return result;
}
private static void search(int digit, int unused, long pow) {
if (digit == 10) {
if (check(pow)) results.add(pow);
return;
}
if (digit == 9) {
digitMultiSet[digit] = unused;
search(digit + 1, 0, pow + unused * pows[digit][N]);
} else {
for (int i = 0; i <= unused; i++) {
digitMultiSet[digit] = i;
search(digit + 1, unused - i, pow + i * pows[digit][N]);
}
}
}
private static boolean check(long pow) {
if (pow >= maxPow) return false;
if (pow < minPow) return false;
int[] testsMultiSet = new int[10];
while (pow > 0) {
int i = (int) (pow % 10);
testsMultiSet[i]++;
pow = pow / 10;
}
for (int i = 0; i < 10; i++) {
if (testsMultiSet[i] != digitMultiSet[i]) return false;
}
return true;
}
/* slow :(
private static boolean isArmstrong(long number) {
String string = String.valueOf(number);
return number == string.chars().map(c -> c - '0').mapToLong(i -> pows[i][string.length()]).sum();
}
*/
private static void print(long a, long[] array, long b) {
System.out.println(Arrays.toString(array));
System.out.printf("memory : %8.3f Mb\n", (Runtime.getRuntime().totalMemory() -
Runtime.getRuntime().freeMemory()) / (8 * 1024 * 1024.0));
System.out.printf("time : %8.3f s\n\n", (b - a) / 1000.0);
}
public static void main(String[] args) {
long a = System.currentTimeMillis();
long[] r = getNumbers(1_000);
long b = System.currentTimeMillis();
print(a, r ,b);
a = System.currentTimeMillis();
r = getNumbers(100_000_000);
b = System.currentTimeMillis();
print(a, r ,b);
}
}