У меня на старинном i5 выдает 4с, а валидатор выдает таймаут. Вывожу все в пределах Long.MAX_VALUE. Неужели это животное по кличке валидатор не есть рекурсии? За читинг с первыми 9 числами не пинайте - они очевидны и считать их не стал. Потратил неделю и 3 таблетки от головной боли. Посоветуйте плиз в чем может быть проблема.
package com.javarush.task.task20.task2025;
import java.math.BigInteger;
import java.util.*;
import java.util.function.LongToIntFunction;
/*
Алгоритмы-числа
*/
public class Solution {
static long [] dpow = new long[190];
static int max_step = 19; // Отладочная константа, сколькозначные максимум числа искать
static TreeSet<Long> armstrongs = new TreeSet<Long>();
static {
// init pow array
for (int i = 1; i < 20; i++) {
for (int j = 0; j < 10; j++) {
dpow[(i - 1) * 10 + j] = (long) Math.pow(j, i);
}
}
dpow[169] = 16677181699666569L;
dpow[179] = 150094635296999121L;
dpow[187] = 11398895185373143L;
dpow[189] = 1350851717672992089L;
}
public static long[] getNumbers(long N) {
List<Integer> lst = new ArrayList<Integer>();
for (int i = 1; i < 10; i++) {
armstrongs.add((long) i);
}
// Основной метод
iterrator(0, 1, lst);
Long[] result = null;
result = armstrongs.toArray(new Long[0]);
// Забрать из result только числа меньше N и скопировать в ответ
long[] tmp_res = new long[result.length];
int k = 0;
for (int i = 0; i < result.length; i++) {
if (result[i] < N) {
tmp_res[i] = result[i];
k++;
}
else break;
}
long[] res = new long[k];
for (int i = 0; i < k; i++) {
res[i] = tmp_res[i];
}
//Arrays.sort(result);
return res;
}
public static void iterrator(int start, int step, List<Integer> lst) {
// Получает уникальные наборы цифр
for (int i = start; i <= 9 ; i++) {
List<Integer> lst_out = new ArrayList<Integer>();
if (step == 1) {
lst_out.add(i);
}
else {
lst_out = new ArrayList<Integer>(lst);
lst_out.add(i);
}
if (step > 1) {
long armstr = isArmstrong(lst_out, step);
if (armstr > 0 ) {
armstrongs.add(armstr);
}
}
if (step < max_step) {
iterrator(i, step + 1, lst_out);
}
}
}
public static int getDigitsCount(long n) {
if (n < 10) return 1;
else if (n < 100) return 2;
else if (n < 1000) return 3;
else if (n < 10000) return 4;
else if (n < 100000) return 5;
else if (n < 1000000) return 6;
else if (n < 10000000) return 7;
else if (n < 100000000) return 8;
else if (n < 1000000000) return 9;
else if (n < 10000000000L) return 10;
else if (n < 100000000000L) return 11;
else if (n < 1000000000000L) return 12;
else if (n < 10000000000000L) return 13;
else if (n < 100000000000000L) return 14;
else if (n < 1000000000000000L) return 15;
else if (n < 10000000000000000L) return 16;
else if (n < 100000000000000000L) return 17;
else if (n < 1000000000000000000L) return 18;
else return 19;
}
public static long mypow(int dgt, int l) {
return dpow[(l - 1) * 10 + dgt];
}
public static long isArmstrong(List<Integer> lst, int step) {
// Проверяет набор цифр на Армстронга, возвращает число Армстронга или -1
long sum = 0;
for (int dgt : lst) {
sum += mypow(dgt, step);
}
long control_sum = 0;
if (getDigitsCount(sum) == step) {
String s = String.valueOf(sum);
byte[] b = String.valueOf(sum).getBytes();
for (byte bb : b) {
control_sum += mypow(bb - 48, step);
}
if (sum == control_sum) return sum;
}
return -1;
}
public static void main(String[] args) {
long a = System.currentTimeMillis();
System.out.println(Arrays.toString(getNumbers(Long.MAX_VALUE)));
long b = System.currentTimeMillis();
System.out.println("memory " + (Runtime.getRuntime().totalMemory() - Runtime.getRuntime().freeMemory()) / (8 * 1024));
System.out.println("time = " + (b - a) / 1000);
}
}