Здравствуйте! Не проходит тест. Пишет, что - "Метод getNumbers должен возвращать массив чисел удовлетворяющих условию задачи". Хотя все значения при различных входных данных проверял, вроде соответствуют эталону. Время работы 6.5 секунд при Long.MAX_VALUE. Правда памяти не знаю сколько получается. Может из-за этого?
package com.javarush.task.task20.task2025;
import java.math.BigInteger;
import java.time.Duration;
import java.time.Instant;
import java.util.*;
/*
Алгоритмы-числа
*/
public class Solution {
private static final long[][] exponents;
private static List<Long> armstrongNumbers;
private static final long[] test = new long[] {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, 4679307774L, 32164049650L, 32164049651L, 40028394225L, 42678290603L,
44708635679L, 49388550606L, 82693916578L, 94204591914L, 28116440335967L, 4338281769391370L,
4338281769391371L, 21897142587612075L, 35641594208964132L, 35875699062250035L, 1517841543307505039L,
3289582984443187032L, 4498128791164624869L, 4929273885928088826L};
static {
exponents = new long[10][20];
for (byte num = 0; num < 10; num++) {
for (int exp = 1; exp < 20; exp++) {
exponents[num][exp] = pow(num, exp);
}
}
}
private static long pow(long val, int exp) {
if (exp == 1) {
return val;
}
return val * pow(val, exp - 1);
}
private static void init() {
armstrongNumbers = new ArrayList<>();
for (long num = 1; num < 10; num++) {
armstrongNumbers.add(num);
}
}
private static long getExp(byte num, int exp) {
return exponents[num][exp];
}
private static boolean check(long sum, long lim, int[] counts, int ranks) {
boolean result = false;
if (sum < lim) {
result = true;
int num;
for (; sum > 0 ; sum /= 10, ranks--) {
num = (int) (sum % 10);
if (counts[num] == 0) {
result = false;
break;
} else {
counts[num]--;
}
}
if (ranks > 0) {
result = false;
}
}
return result;
}
private static void writeArmstrongNumber(byte[] set, long lim) {
long sum = 0;
long exp;
int[] counts = new int[10];
for (byte b : set) {
exp = getExp(b, set.length);
if (Long.MAX_VALUE - exp < sum) {
return;
}
sum += exp;
counts[b]++;
}
if (check(sum, lim, counts, set.length)) {
armstrongNumbers.add(sum);
}
}
private static void computeRank(List<byte[]> sets, int maxRanks, long lim) {
if (sets.get(0).length >= maxRanks) {
return;
}
List<byte[]> newSets = new ArrayList<>();
byte[] newSet = new byte[0];
for (byte[] set : sets) {
for (byte last = set[set.length - 1]; last >= 0; last--) {
newSet = Arrays.copyOf(set, set.length + 1);
newSet[set.length] = last;
newSets.add(newSet);
writeArmstrongNumber(newSet, lim);
}
}
sets = null;
computeRank(newSets, maxRanks, lim);
}
public static long[] getNumbers(long N) {
if (N <= 1) {
return new long[0];
}
if (N < 10) {
long[] res = new long[(int) N - 1];
for (int i = 0, j = i + 1; i < res.length; i++, j++) {
res[i] = j;
}
return res;
}
init();
List<byte[]> sets = new ArrayList<>();
for (byte i = 1; i < 10; i++) {
sets.add(new byte[]{i});
}
computeRank(sets, String.valueOf(N).length(), N);
return armstrongNumbers.stream().mapToLong(l -> l).sorted().toArray();
}
public static void main(String[] args) {
//Instant inst = Instant.now();
long l = getPositiveLong();
System.out.println(l);
System.out.println(Arrays.equals(getArray(l), getNumbers(l)));
//System.out.println(Arrays.toString(getNumbers(l)));
//System.out.println(Duration.between(inst, Instant.now()));
}
private static long getPositiveLong() {
long l = new Random().nextLong();
return l < 0 ? ~l : l;
}
private static long[] getArray(long lim) {
int j = test.length;
for (int i = 0; i < test.length; i++) {
if (test[i] >= lim) {
j = i;
break;
}
}
return Arrays.copyOf(test, j);
}
}
// 1, 2, 3, 4, 5, 6, 7, 8, 9,
// 153, 370, 371, 407,
// 1634, 8208, 9474,
// 54_748, 92_727, 93_084,
// 548_834,
// 1_741_725, 4_210_818, 9_800_817, 9_926_315,
// 24_678_050, 24_678_051, 88_593_477,
// 146_511_208, 472_335_975, 534_494_836, 912_985_153,
// 4_679_307_774,
// 32_164_049_650, 32_164_049_651, 40_028_394_225, 42_678_290_603, 44_708_635_679, 49_388_550_606, 82_693_916_578, 94_204_591_914,
// 28_116_440_335_967,
// 4_338_281_769_391_370, 4_338_281_769_391_371,
// 21_897_142_587_612_075, 35_641_594_208_964_132, 35_875_699_062_250_035,
// 1_517_841_543_307_505_039, 3_289_582_984_443_187_032, 4_498_128_791_164_624_869, 4_929_273_885_928_088_826