Да да, код еще не оптимизирован. Но все же, уже второй день дебажу и не могу понять, почему находит не все числа?
Реализация по принципу:
1. Матрица чисел 1-9 со степенями до длины числа N
2 Создание уникальных чисел в массиве, длинной, равной числу N и заполненом цифрой 9.
3 Суммирование чисел, вытягивая суммы из матрицы степеней и попутно проверяя на соответсвие длине числа N
Зараннее спасибо!
package com.javarush.task.task20.task2025;
import java.math.BigDecimal;
import java.math.BigInteger;
import java.util.*;
/*
Алгоритмы-числа
*/
public class Solution {
static long[][] arrayWithPowers;
static long numbersize;
static Set<Long> setOdNumbers = new TreeSet<>();
public static void createPowerArray(long N) { // initializes arrayWithPowers with [][]array of calculated matrix of powers
int size = String.valueOf(N).length(); // dlina massiva stiepitniej ( maks kolichestwo stepeniej w massivie)
long[][] array = new long[size][10];
for (int i = 0; i < array.length; i++) {
for (int j = 0; j < array[i].length; j++) {
array[i][j] = (long) Math.pow(j, i + 1);
// System.out.print(array[i][j] + " ");
}
// System.out.println("");
}
arrayWithPowers = array;
}
public static void inversion(int[] array, int i) {// umienshajet matricu poluchaja kombinacyji unikalnych cyfr
if (array[array.length - 1] == 0) return;
if (array[i] > 0) array[i]--;
else if (array[i] == 0) {
int a = i + 1;
inversion(array, a);
array[i] = array[i + 1];
}
}
public static void countArmstrongNumbers(int[] array, int j) { // ischet armstrong numbers dla peredannoj matricy
BigInteger bigInteger = new BigInteger("0");
if (array[j] == 0) countArmstrongNumbers(array, j + 1);
int i = j;
long sum = 0;
int power = array.length - i;
for (; i < array.length; i++) {
if(power >18){
bigInteger = bigInteger.add(new BigInteger(String.valueOf(arrayWithPowers[power - 1][array[i]])));
sum = bigInteger.intValue();
}else{
sum += arrayWithPowers[power - 1][array[i]];
}
}
if (String.valueOf(sum).length() == power) { // jesli dlina sumy bolshe chem stepien (chem chislo)
String[] second = String.valueOf(sum).split("");
long sum2 = 0;
for (int k = 0; k < second.length; k++) {
sum2 += arrayWithPowers[second.length - 1][Integer.parseInt(second[k])];
}
if (sum == sum2 && sum < numbersize) {
setOdNumbers.add(sum);
}
}
}
public static long[] getNumbers(long N) {
String chislo =String.valueOf(N);
createPowerArray(N);
int size = chislo.length();
numbersize = N;
int[] uniqueNumbers = new int[size]; // dlina chisla N
Arrays.fill(uniqueNumbers, 9);
while ((uniqueNumbers[uniqueNumbers.length - 1]) != 0) {
countArmstrongNumbers(uniqueNumbers, 0);
inversion(uniqueNumbers, 0);
}
long[] result = new long[setOdNumbers.size()];
int i = 0;
for(Long l: setOdNumbers){
result[i] = l;
i++;
}
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);
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);
}
}