Всем привет. Пытаюсь разобраться с задачей без массива заполненного готовыми значениями.
Вот что получилось.
package com.javarush.task.task20.task2025;
import java.util.Arrays;
import java.util.Iterator;
import java.util.TreeSet;
/*
Алгоритмы-числа
*/
public class Solution {
public static long [][] arrayDegree = new long[9][19];
public static long getDegreeNamber(long x, int y){
long rezultat = x;
for (int i = 0; i < y; i++) {
rezultat = rezultat * x;
}
return rezultat;
}
public static void fillArrayDegree(){
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 19; j++) {
arrayDegree[i][j] = i + 1;
arrayDegree[i][j] = getDegreeNamber(arrayDegree[i][j],j);
}
}
}
public static int getExponentNamber(long x){
int exponent = 0;
while (x > 0){
x = x / 10;
exponent++;
}
return exponent;
}
public static void fillArray(int[] array, int namber, int start, int finish){
for (int i = start; i < finish; i++) {
array[i] = namber;
}
}
public static boolean decrementArray (int[] array){
int index = 0;
while (index < array.length && array[index] == 0){
index++;
}
if(index + 1 == array.length && array[index] == 1){
return false;
}
fillArray(array, array[index] - 1, 0, index + 1);
return true;
}
public static long generateNambers(int[] array, int exponent){
long x = 0;
for (int i = 0; i < array.length; i++) {
if(array[i] == 0) {
continue;
}
x = x + arrayDegree[array[i] - 1][exponent - 1];
}
return x;
}
public static long generateNambers(long x){
int exponent = getExponentNamber(x);
long y = 0;
while (x > 0){
for (int i = 0; i < exponent; i++) {
while (x % 10 == 0) {
x = x / 10;
i++;
}
y = y + arrayDegree[(int)(x % 10) - 1 ] [exponent - 1];
x = x / 10;
}
if(y < 0){
return -1;
}
}
return y;
}
public static long[] getNumbers(long N) {
if(N <= 0){
long[] result = new long[0];
return result;
}
fillArrayDegree();
TreeSet<Long> listNambers = new TreeSet<Long>();
int poridok = getExponentNamber(N);
int [] masiv = new int[poridok];
fillArray(masiv, 9, 0, poridok);
while (decrementArray(masiv)){
poridok = getExponentNamber(N);
long x = generateNambers(masiv,poridok);
while (poridok > 0){
x = generateNambers(masiv, poridok--);
if( x == generateNambers(x) && x < N && x > 0){
listNambers.add(x);
}
}
}
long [] result = new long[listNambers.size()];
Iterator<Long> itr = listNambers.iterator();
int i = 0;
while (itr.hasNext()){
result[i] = itr.next();
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);
}
}
По валидатору не проходит вот такой пункт
Метод getNumbers должен возвращать массив чисел удовлетворяющих условию задачи.
Я проверял разные значения N вроде выдаёт правильный массив лонгов.
Подскажите где я ошибся? package com.javarush.task.task20.task2025;
import java.util.Arrays;
import java.util.Iterator;
import java.util.TreeSet;
/*
Алгоритмы-числа
*/
public class Solution {
public static long [][] stepeniChisel = new long[9][19];
public static long vozvedenieVStepen(long x, int y){
long rezultat = x;
for (int i = 0; i < y; i++) {
rezultat = rezultat * x;
}
return rezultat;
}
public static void fillStepeniChisel (){
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 19; j++) {
stepeniChisel[i][j] = i + 1;
stepeniChisel[i][j] = vozvedenieVStepen(stepeniChisel[i][j],j);
}
}
}
public static int getStepen (long x){
int stepen = 0;
while (x > 0){
x = x / 10;
stepen++;
}
return stepen;
}
public static void fill (int[] masiv, int namber, int start, int finish){
for (int i = start; i < finish; i++) {
masiv[i] = namber;
}
}
public static boolean decrementArray (int[] masiv){
int index = 0;
while (index < masiv.length && masiv[index] == 0){
index++;
}
if(index + 1 == masiv.length && masiv[index] == 1){
return false;
}
fill(masiv, masiv[index] - 1, 0, index + 1);
return true;
}
public static long generateChislo (int[] masiv, int poriadok){
long x = 0;
for (int i = 0; i < masiv.length; i++) {
if(masiv[i] == 0) {
continue;
}
x = x + stepeniChisel[masiv[i] - 1][poriadok - 1];
}
return x;
}
public static long generateChislo (long x){
int poriadok = getStepen(x);
long y = 0;
while (x > 0){
for (int i = 0; i < poriadok; i++) {
while (x % 10 == 0) {
x = x / 10;
i++;
}
y = y + stepeniChisel[(int)(x % 10) - 1 ] [poriadok - 1];
x = x / 10;
}
if(y < 0){
return -1;
}
}
return y;
}
public static long[] getNumbers(long N) {
if(N < 1){
long[] result = new long[0];
return result;
}
fillStepeniChisel();
for (int i = 0; i < stepeniChisel.length; i++) {
System.out.println(Arrays.toString(stepeniChisel[i]));
}
TreeSet<Long> kollekciya = new TreeSet<Long>();
int poridok = getStepen(N);
int [] masiv = new int[poridok];
fill(masiv, 9, 0, poridok);
while (decrementArray(masiv)){
poridok = getStepen(N);
long x = generateChislo(masiv,poridok);
while (poridok > 0){
x = generateChislo(masiv, poridok--);
if( x == generateChislo(x) && x < N && x > 0){
kollekciya.add(x);
}
}
}
long [] result = new long[kollekciya.size()];
Iterator<Long> itr = kollekciya.iterator();
int i = 0;
while (itr.hasNext()){
result[i] = itr.next();
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);
}
}