Що йому не так. Массив правильний показники часу і пам'яті в нормі. Що йому не так на цей раз?
package ua.javarush.task.task20.task2025;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
/*
Алгоритми-числа
*/
public class Solution {
private static long[][] pows;
private static void precalculatePows(int maxPow){
pows = new long[11][maxPow + 1];
for (int i = 0; i <= 10; i++){
pows[i][0] = 1;
for (int j = 1; j <= maxPow; j++){
pows[i][j] = pows[i][j-1] * i;
}
}
}
public static long[] getNumbers(long N) {
List<Long> armstongNumbers = new ArrayList<>();
int maxPow = 0;
long limit = 1;
while (limit < N){
maxPow++;
limit *= 10;
}
List<int[]> combinations = new ArrayList<>();
precalculatePows(maxPow);
for(int n = 1; n <= maxPow; n++){
generateCombinations(n, combinations);
}
for (int[] combination: combinations){
long number = toArmstrong(combination);
if(number != -1 && number < N) armstongNumbers.add(number);
}
Collections.sort(armstongNumbers);
long[] result = new long[armstongNumbers.size()];
for (int i = 0; i < armstongNumbers.size(); i++) {
result[i] = armstongNumbers.get(i);
}
return result;
}
private static void generateCombinations(int n, List<int[]> combinations) {
int[] combination = new int[n];
for (int i = 9; i >= 1 ; i--) {
combination[0] = i;
generateHelper(combination, 0, i, combinations);
}
}
private static void generateHelper(int[] combination, int combinationIndex, int maxDigit, List<int[]> result) {
int currentPow = combination.length;
long number = 0;
for (int i = 0; i <= combinationIndex; i++) {
number += pows[combination[i]][currentPow];
}
long min = number + pows[maxDigit][currentPow] * (currentPow - combinationIndex -1);
if (min < pows[10][currentPow - 1]) return;
if(combinationIndex == currentPow - 1) {
result.add(Arrays.copyOf(combination, combination.length));
return;
}
for (int i = maxDigit; i >= 0 ; i--) {
if((number + pows[i][currentPow]) > pows[10][currentPow]) continue;
combination[combinationIndex + 1] = i;
generateHelper(combination, combinationIndex + 1, i, result);
}
}
private static long combinationToSum(int[] combination){
long number = 0;
int currentPow = combination.length;
for (int i = 0; i < combination.length; i++) {
number += pows[combination[i]][currentPow];
}
return number;
}
private static long toArmstrong(int[] combination){
long number = combinationToSum(combination);
StringBuilder numberString = new StringBuilder(Long.toString(number));
for (int n: combination){
String crN = Integer.toString(n);
int position = numberString.indexOf(crN);
if(position == -1) return -1;
numberString.delete(position, position + 1);
}
return number;
}
public static void main(String[] args) {
long a = System.currentTimeMillis();
System.out.println(Arrays.toString(getNumbers(1000)));
long b = System.currentTimeMillis();
System.out.println("memory " + (Runtime.getRuntime().totalMemory() - Runtime.getRuntime().freeMemory()) / (8 * 1024));
System.out.println("time = " + (b - a) / 1000);
a = System.currentTimeMillis();
System.out.println(Arrays.toString(getNumbers(1000000)));
b = System.currentTimeMillis();
System.out.println("memory " + (Runtime.getRuntime().totalMemory() - Runtime.getRuntime().freeMemory()) / (8 * 1024));
System.out.println("time = " + (b - a) / 1000);
}
}