но последнее условие пишет что не хватает элементов или есть лишние.
подскажите как можно оптимизировать или я вообще не тем путем пошёл? и логика проверки что-ли не верна. для того чтобы не пропустить числа с 0 типа 370 генерировал невозрастающие числа, а не неубывающие. или я тут маху дал, потому что тогда на каждый десяток будет тратиться расчетное время и память? но я не могу придумать как тогда такие числа как 370 проверять.
package com.javarush.task.task20.task2025;
import java.util.Arrays;
import java.util.List;
import java.util.ArrayList;
import java.util.Set;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Collections;
/*
Алгоритмы-числа
*/
public class Solution {
static long[][] powers = new long[10][20] ;
static{ for(int i=0; i<10; i++){
for(int j=0; j<20;j++){
if((i==0 || i==1) && j>0){
powers[i][j] = i;
}else if(j==0){
powers[i][j]=1;
}else if(i==0 || i==1){
powers[i][j]=i;
} else{
long x = 1;
for(int c=0; c<j; c++){
x*=i;
}
powers[i][j]=x;
}
}
}
}
public static long[] getNumbers(long N) {
long[] result = null;
if(N<=0) return result;
Set<Long> set = new HashSet<>();
Queue<Long> queue = new LinkedList<>();
for (long i = 1; i <= 9; i++){
queue.add( i);
}
long firstLimit = N/10;
byte secondLimit = (byte)(N%10);
while (!queue.isEmpty()) {
long number = queue.poll();
long someNumber = examineOfArmstrong(number, N, powers);
if(someNumber>0){
set.add(someNumber);
}
byte lastDigit = (byte) (number % 10);
for (byte nextDigit = 0; nextDigit <= lastDigit; nextDigit++){
if (number > firstLimit || (number == firstLimit && nextDigit > secondLimit)){
break;}
long nextNumber = number*10+nextDigit;
if(nextNumber>0) queue.add(nextNumber) ;
}
}
int count = set.size();
result = new long[count];
List<Long> list = new ArrayList<>(set);
Collections.sort(list);
for(int i=0;i<count; i++){
result[i]=list.get(i);
}
return result;
}
public static long examineOfArmstrong(long number, long N, long[][] powers){
byte countOfDigits = countDigits(number);
byte[] digits= new byte[countOfDigits];
long tempNumber = number;
long sum = 0;
byte digit = 0;
byte index1 = 0;
while(tempNumber>0){
digit = (byte)(tempNumber%10);
digits[index1]= digit;
index1++;
sum+= powers[digit][countOfDigits];
tempNumber/=10;
if (sum==N || sum<0) return (long)-1;
}
if (sum>=N || sum<0) return (long)-1;
if(sum==number) return number;
countOfDigits = countDigits(sum);
tempNumber = sum;
byte[] digitsOfSum = new byte[countOfDigits];
byte index2 = 0;
while(tempNumber>0){
digit =(byte)(tempNumber%10);
digitsOfSum[index2] = digit;
index2++;
tempNumber/=10;
}
Arrays.sort(digits);
Arrays.sort(digitsOfSum);
if(Arrays.equals(digits, digitsOfSum)) return sum;
return (long)-1;
}
private static byte countDigits(long number){
if(number==0) return 1;
byte count = 0;
long temp = number;
while(temp>0){
temp/=10;
count++;
}
return count;
}
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(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);
}
}