Добрый времени суток, коллеги!
Потратил неприлично много времени на эту задачу, но не могу позволить себе все бросить, а идеи уже закончились куда копать? Не проходит по последнему пункту.
package com.javarush.task.task20.task2025;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.TreeSet;
/*
Алгоритмы-числа
*/
public class Solution {
private static long[][] pows = new long[10][20];
static {
for (int i = 0; i < pows.length; i++) {
long p = 1;
for (int j = 0; j < pows[i].length; j++) {
pows[i][j] = p;
p *= i;
}
}
}
static boolean decrementArray() {
int index = 0;
while (index < longs.length && longs[index] == 0) {
index++;
}
if (index + 1 == longs.length && longs[index] == 1) {
return false;
}
Arrays.fill(longs, 0, index + 1, longs[index] - 1);
return true;
}
private static ArrayList<Long> numbers = new ArrayList<>();
private static TreeSet<Long> res = new TreeSet<>();
private static ArrayList<Long> tempArray = new ArrayList<>();
private static long temp;
private static long number;
private static long armstrongNum;
private static long[] result;
private static long[] longs;
//вычисление степенной суммы
private static long getPowSum(long[] intArray) {
for (int i = 0; i < intArray.length; i++) {
number += pows[(int) intArray[i]][intArray.length];
}
return number;
}
private static long getPowSum(ArrayList<Long> numbers) {
for (int j = 0; j < numbers.size(); j++) {
armstrongNum += pows[Math.toIntExact(numbers.get(j))][numbers.size()];
}
return armstrongNum;
}
//разделяем число на цифры
private static void getNums(long temp) {
while (temp > 0) {
numbers.add(temp % 10);
temp /= 10;
}
Collections.reverse(numbers);
}
//получаем массив чисел Армстронга
public static long[] getNumbers(long N) {
if (N <= 0 || N == 1) {
result = new long[0];
return result;
}
longs = new long[(int) Math.ceil(Math.log10(N))];
Arrays.fill(longs, 9);
while (decrementArray()) {
if (longs[0] == 0) {
for (long i : longs) {
tempArray.add(i);
}
while (tempArray.get(0) == 0) {
armstrongNum = 0;
number = 0;
numbers.clear();
getPowSum(tempArray);
number = armstrongNum;
armstrongNum = 0;
temp = number;
if (temp > 0) {
getNums(temp);
if (numbers.size() < 20) {
getPowSum(numbers);
if (armstrongNum == number && armstrongNum < N) {
res.add(armstrongNum);
}
}
}
temp = 0;
tempArray.remove(0);
}
if (tempArray.get(0) != 0) {
armstrongNum = 0;
number = 0;
numbers.clear();
getPowSum(tempArray);
number = armstrongNum;
armstrongNum = 0;
temp = number;
if (temp > 0) {
getNums(temp);
if (numbers.size() < 20) {
getPowSum(numbers);
if (armstrongNum == number && armstrongNum < N) {
res.add(armstrongNum);
}
}
}
}
} else {
getPowSum(longs);
temp = number;
if (temp > 0) {
getNums(temp);
if (numbers.size() < 20) {
getPowSum(numbers);
if (armstrongNum == number && armstrongNum < N) {
res.add(armstrongNum);
}
}
}
}
temp = 0;
number = 0;
armstrongNum = 0;
numbers.clear();
tempArray.clear();
}
result = new long[res.size()];
int index = 0;
for (long l : res) {
result[index] = l;
index++;
}
res.clear();
return result;
}
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);
}
}