Друзья, никак не могу понять, что не так.
В выводе 50 чисел (те, что нужны), отрабатывает за 6-7 секунд и требует 6 мегабайт памяти.
И все же, что то не так!
Помогите пожалуйста разоабраться. Вывод для 0 и long.max_value:
[]
memory 256
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, 146511208, 472335975, 534494836, 912985153, 4679307774, 32164049650, 32164049651, 40028394225, 42678290603, 44708635679, 49388550606, 82693916578, 94204591914, 28116440335967, 4338281769391370, 4338281769391371, 21897142587612075, 35641594208964132, 35875699062250035, 1517841543307505039, 3289582984443187032, 4498128791164624869, 4929273885928088826]
memory 6266
time = 7package com.javarush.task.task20.task2025;
import java.sql.Array;
import java.sql.SQLOutput;
import java.util.*;
/*
Алгоритмы-числа
*/
public class Solution {
public static long[][] pow;
public static int digCount;
public static long[] getNumbers(long N) {
pow = null;
ArrayList<Long> results = new ArrayList<>();
digCount = digCount(N);
pow = getPow(digCount);
if(N <= 0) return new long[0];
//GENERATING UNIQUE NUMBERS
int[] numArray = generateArray(N);
ArrayList<Long> list = new ArrayList<>();
long arm;
for (int i = 0; i < numArray.length-1; i++) {
while (numArray[i+1] > 0){
while (numArray[i]> 0 ){
numArray[i]--;
arm = checkArmNumExtended(numArray);
if (arm != -1 && arm < N && !list.contains(arm) && arm !=0) list.add(arm);
}
numArray[i+1]--;
for (int j = 0; j <= i; j++) {
numArray[j]= numArray[i+1]; //проверить нужны ли нули
arm = checkArmNumExtended(numArray);
if (arm != -1 && arm < N && !list.contains(arm) && arm !=0) list.add(arm);
}
for (int j = 0; j <= i; j++) {
if (numArray[j] !=0){
i=j;
continue;
};
}
}
}
// for (int[] i : list){
//// long sum = powSum(i);
//// if (digCount(sum) > digCount) continue;
// long arm = checkArmNumExtended(i);
// if (arm != -1 && arm < N && !results.contains(arm) && arm !=0){
// results.add(arm);
// }
// }
Collections.sort(list);
long[] result = new long[list.size()];
for (int i = 0; i < result.length; i++) {
result[i] = list.get(i);
}
pow = null;
return result;
}
// public static int[] decrement(int[] num, int i) {
// int[] result = num;
// for (int j = 0; j < i; j++) {
// while (result[j+1]> 0) {
// while (result[j] > 0) {
// result[j]--;
// System.out.println(Arrays.toString(result));
// }
// result[j+1]--;
// for (int k = 0; k <= j; k++) {
// result[k] = result[j+1];
// }
// System.out.println(Arrays.toString(result));
// result = decrement(result, j);
// }
//
// }
// return result;
// }
public static int[] generateArray (long num){
int[] array = new int[digCount];
for (int i = 0; i < digCount; i++) {
array[i] = 9;
}
return array;
}
public static int digCount (long number){
int count = (number==0 ? 1: 0);
while (number!=0){
count++;
number /=10;
}
return count;
}
public static long[][] getPow(int digits){ //заполнение матрицы степеней чисел 0-9
long[][] result = new long[10][digits+1];
for (int i = 0; i < 10; i++) {
for (int j = 1; j <= digits; j++) {
result[i][j] = pow(i, j);
}
}
return result;
}
public static long pow (int base, int pow){ //возведение в степень
long result = 1;
for (int i = 1; i <= pow; i++) {
result *= base;
}
return result;
}
// public static boolean checkNum (long num){ //проверка на предмет возрастания разрядов в числе
// boolean result = true;
// char[] string = String.valueOf(num).toCharArray();
// int size = string.length;
// int arr[] = new int[size];
//
// for (int i = 0; i < size; i++) {
// arr[i] = Integer.parseInt(String.valueOf(string[i]));
// }
// for (int i = 1; i < arr.length-1; i++) {
// if (((arr[i] > arr[i+1]))){
// result = false;
// }
// }
// return result;
// }
// public static long powSum (long num){ //степенная сумма числа
// long sum = 0;
// char[] string = String.valueOf(num).toCharArray();
//
// for (int i = 0; i < string.length; i++) {
// sum = sum + pow[Integer.parseInt(String.valueOf(string[i]))][digCount(num)];
// }
// return sum;
// }
public static long powSum (int[] num){
long sum=0;
for (int i = 0; i < num.length; i++) {
sum += pow[num[i]][num.length];
}
if (digCount(sum) > digCount) return 0;
return sum;
}
public static long checkArmNumExtended (int[] num){
long result = -1;
long sum;
long arm;
for (int i = 0; i < num.length; i++) {
if (num[i]==0) {
sum = powSum(Arrays.copyOfRange(num, i+1, num.length));
arm = checkArmNum(sum);
if (arm!=-1){
return arm;
}
}
}
sum = powSum(num);
arm = checkArmNum(sum);
if (arm != - 1){
return arm;
}
else return result;
}
public static long checkArmNum(long num){ //проверка является ли число числом Армстронга
long l = num;
long sum = 0;
int digcount = digCount(num);
while (l > 0){
long div = l%10;
int ntDiv = (int)div;
sum = sum + pow[ntDiv][digcount];
l = l/10;
}
if (num==sum){
return num;
}
else {return -1;}
}
public static void main(String[] args) {
long a = System.currentTimeMillis();
System.out.println(Arrays.toString(getNumbers(-1)));
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(Long.MAX_VALUE)));
b = System.currentTimeMillis();
System.out.println("memory " + (Runtime.getRuntime().totalMemory() - Runtime.getRuntime().freeMemory()) / (8 * 1024));
System.out.println("time = " + (b - a) / 1000);
}
}