Для Long.MAX_VALUE возвращаются все числа Армстронга но валидатор не пускает.
результат:
size:50
time: 6590 ms
memory: 58 MB
package com.javarush.task.task20.task2025;
import java.util.ArrayList;
import java.util.Collections;
/*
Алгоритмы-числа
*/
public class Solution {
public static long arr[][] = null;
public static long[] getNumbers(long N) {
long[] result = null;
int len = String.valueOf(N).length();
if (len > 20 || len == 0) {
return result;
}
ArrayList<Long> listArms = new ArrayList<Long>();
fillPow(N); //заполняем массив степеней
long[] srchArray = generateSearchArray(N); //заполняем массив для поиска чисел Армстронга
for (long i = 0; i < srchArray.length; i++) {
long mulVal = 1; //переменная для добавление нулей
while (true) { //цикл используется для проверки чисел с нулями в конце
long checkVal = srchArray[(int) i] * mulVal; //число для проверки
if (checkVal >= N || checkVal < 0) { //если вышли за диапазон - выход из цикла
break;
}
long nums[] = getNums(checkVal); // получаем масив цифр
int power = nums.length;
long powVal = getPow(power, nums); // получаем сумму степеней
if (powVal != checkVal && powVal > 0) { // если не число Армстронга проверяем полученое число
checkVal = powVal;
nums = getNums(powVal);
power = nums.length;
powVal = getPow(power, nums);
}
if (powVal < 0) { //если вышли за диапазон - выход из цикла
break;
}
if (powVal == checkVal) { // если число Армстронга - заносим в список и переходим к след. числу
if (!listArms.contains(powVal)) {
listArms.add(powVal);
}
break;
}
mulVal *= 10; // если не число армстрога - добавляем ноль и проверяем дальше
}
}
result = new long[listArms.size()];
Collections.sort(listArms);
for (int idx = 0; idx < listArms.size(); idx++) {
result[idx] = listArms.get(idx);
}
System.gc();
return result;
}
//заполняем массив степеней
public static void fillPow(long N) {
int len = String.valueOf(N).length();
long digitPow;
arr = new long[9][len + 1];
for (int i = 1; i <= 9; i++) {
digitPow = 1;
for (int j = 1; j <= len + 1; j++) {
arr[i - 1][j - 1] = digitPow;
digitPow *= i;
}
}
}
public static long getPow(int power, long nums[]) {
long val = 0;
for (int j = 0; j < power; j++) {
int dig = (int) nums[j];
if (dig > 0 && power >= 1 && power < 20) {
val += arr[dig - 1][power];
}
}
return val;
}
public static long[] getNums(long number) {
int len = String.valueOf(number).length();
long nums[] = new long[len];
int i = 0;
while (number != 0) {
nums[i] = number % 10;
number /= 10;
i++;
}
return nums;
}
//заполняем массив для поиска чисел Армстронга
public static long[] generateSearchArray(long N) {
ArrayList<Long> list = new ArrayList<>();
long mainRank = 0;
int numDigit = String.valueOf(N).length();
long i = 1;
while (i < N) {
list.add(i);
/*
if (i > 10) {
long addVal = 1;
int digit = String.valueOf(i).length();
for (int j = digit; j < numDigit; j++) {
addVal *= 10;
long valAndZero = i * addVal;
if (valAndZero > i && valAndZero < N) {
list.add(valAndZero);
}
}
}
*/
if (i % 10 != 9) {
i++;
} else {
long curentNumber = i;
int digit = 1;
while (true) {
curentNumber = curentNumber / 10;
if (curentNumber % 10 != 9) {
break;
}
digit++;
}
mainRank = 0;
if (curentNumber > 10) {
mainRank = curentNumber / 10;
curentNumber %= 10;
}
curentNumber++;
long nextIdx = curentNumber;
long factor = 10;
for (int j = 0; j < digit; j++) {
nextIdx = nextIdx + curentNumber * factor;
factor *= 10;
}
nextIdx += mainRank * factor;
if (nextIdx < i) {
break;
}
i = nextIdx;
}
}
Collections.sort(list);
long srchArray[] = new long[list.size()];
for (int idx = 0; idx < list.size(); idx++) {
srchArray[idx] = list.get(idx);
}
return srchArray;
}
public static void main(String[] args) {
long start = System.currentTimeMillis();
long[] result = null;
//long[] srchArray = generateSearchArray(Long.MAX_VALUE); //534 ms
// result = getNumbers( 0); //999999999999999999
result = getNumbers(Long.MAX_VALUE);
long end = System.currentTimeMillis();
if (result != null) {
for (int i = 0; i < result.length; i++) {
System.out.println(result[i]);
}
System.out.println("size:" + result.length);
}
System.out.println("time: " + (end - start));
System.out.println("memory: " + (Runtime.getRuntime().totalMemory() - Runtime.getRuntime().freeMemory()) / 1000000 + " MB");
}
}