getNumbers(Long.MAX_VALUE)
ОК - 1 = 1
ОК - 2 = 2
ОК - 3 = 3
ОК - 4 = 4
ОК - 5 = 5
ОК - 6 = 6
ОК - 7 = 7
ОК - 8 = 8
ОК - 9 = 9
ОК - 153 = 153
ОК - 370 = 370
ОК - 371 = 371
ОК - 407 = 407
ОК - 1634 = 1634
ОК - 8208 = 8208
ОК - 9474 = 9474
ОК - 54748 = 54748
ОК - 92727 = 92727
ОК - 93084 = 93084
ОК - 548834 = 548834
ОК - 1741725 = 1741725
ОК - 4210818 = 4210818
ОК - 9800817 = 9800817
ОК - 9926315 = 9926315
ОК - 24678050 = 24678050
ОК - 24678051 = 24678051
ОК - 88593477 = 88593477
ОК - 146511208 = 146511208
ОК - 472335975 = 472335975
ОК - 534494836 = 534494836
ОК - 912985153 = 912985153
ОК - 4679307774 = 4679307774
ОК - 32164049650 = 32164049650
ОК - 32164049651 = 32164049651
ОК - 40028394225 = 40028394225
ОК - 42678290603 = 42678290603
ОК - 44708635679 = 44708635679
ОК - 49388550606 = 49388550606
ОК - 82693916578 = 82693916578
ОК - 94204591914 = 94204591914
ОК - 28116440335967 = 28116440335967
ОК - 4338281769391370 = 4338281769391370
ОК - 4338281769391371 = 4338281769391371
ОК - 21897142587612075 = 21897142587612075
ОК - 35641594208964132 = 35641594208964132
ОК - 35875699062250035 = 35875699062250035
ОК - 1517841543307505039 = 1517841543307505039
ОК - 3289582984443187032 = 3289582984443187032
ОК - 4498128791164624869 = 4498128791164624869
ОК - 4929273885928088826 = 4929273885928088826
getNumbers(0)
[]
getNumbers(1)
[]
getNumbers(370)
[1, 2, 3, 4, 5, 6, 7, 8, 9, 153]
package com.javarush.task.task20.task2025;
import com.sun.org.apache.xerces.internal.impl.xpath.regex.Match;
import java.util.*;
import java.util.regex.Matcher;
import java.util.regex.Pattern;
/*
Алгоритмы-числа
Число S состоит из M цифр, например, S=370 и M (количество цифр) = 3
Реализовать логику метода getNumbers, который должен среди натуральных чисел меньше N (long)
находить все числа, удовлетворяющие следующему критерию:
число S равно сумме его цифр, возведенных в M степень
getNumbers должен возвращать все такие числа в порядке возрастания.
Пример искомого числа:
370 = 3*3*3 + 7*7*7 + 0*0*0
8208 = 8*8*8*8 + 2*2*2*2 + 0*0*0*0 + 8*8*8*8
На выполнение дается 10 секунд и 50 МБ памяти.
Требования:
1. В классе Solution должен присутствовать метод getNumbers c одним параметром типа long.
2. Метод getNumbers должен быть публичным.
3. Метод getNumbers должен быть статическим.
4. Метод getNumbers должен возвращать массив чисел удовлетворяющих условию задачи.
*/
public class Solution {
public static Pattern pattern = Pattern.compile("([0-9]*)([1-9])(0+\\b)");
public static long[][] powers = new long[10][20]; // [x: 1..9][power:1..19]
public static long[] getNumbers(long N) {
long[] arrayOfResults = null;
List<Long> listOfResults = new ArrayList<Long>();
// if (N>0) {
// listOfResults.add(0L);
// }
for (long i = 1; i < N; ) {
long sum = calculatedSum(i);
if (sum == i) {
if (!listOfResults.contains(sum) && sum < N) {
listOfResults.add(sum);
}
} else {
long sumCheck = sum;
sum = calculatedSum(sumCheck);
if (sumCheck == sum && !listOfResults.contains(sum) && sum < N) {
listOfResults.add(sum);
}
}
if (i % 10 == 0) {
i = nextNumberUp(i);
continue;
} else {
i++;
}
}
Collections.sort(listOfResults);
arrayOfResults = listOfResults.stream().mapToLong(l -> l).toArray(); // https://stackoverflow.com/questions/6175004/what-is-the-best-way-of-converting-listlong-object-to-long-array-in-java
return arrayOfResults;
}
public static void raisePowers() {
for (int i = 1; i < 10; i++) {
powers[i][1] = i;
}
for (int j = 1; j < 20; j++) {
powers[1][j] = 1;
}
for (int i = 2; i < 10; i++) {
for (int j = 2; j < 20; j++) {
powers[i][j] = powers[i][j - 1] * i;
}
}
}
public static long nextNumberUp(long x) {
Matcher matcher = pattern.matcher(String.valueOf(x));
matcher.find();
String s = matcher.group(1);
for (int i = 0; i < matcher.group(3).length() + 1; i++) {
s += matcher.group(2);
}
if (matcher.group(3).length() == 2) {
s = s.substring(0, s.length() - 1) + "0";
} else if (matcher.group(3).length() == 3) {
s = s.substring(0, s.length() - 2) + "00";
} else if (matcher.group(3).length() > 3) {
s = s.substring(0, s.length() - 3) + "000";
}
long l;
try {
l = Long.parseLong(s);
if (l < 0) {
l = Long.MAX_VALUE;
}
} catch (Exception e) {
l = Long.MAX_VALUE;
}
return l;
}
public static long calculatedSum(Long x) {
char[] mas = x.toString().toCharArray();
int power = mas.length;
long sum = 0L;
for (int i = 0; i < power; i++) {
if (mas[i] != 48) {
try {
sum += powers[Integer.parseInt(String.valueOf(mas[i]))][power];
} catch (Exception e) {
sum = Long.MAX_VALUE;
return sum;
}
}
}
return sum;
}
public static void main(String[] args) {
long start = new Date().getTime();
raisePowers();
long[] mas1 = getNumbers(Long.MAX_VALUE);
long finish = new Date().getTime();
System.out.println("past time (ms): " + (finish - start));
long[] test = {1, 2, 3, 4, 5, 6, 7, 8, 9, 153, 370, 371, 407, 1634, 8208, 9474,
54748, 92727, 93084, 548834, 1741725, 4210818, 9800817, 9926315, 24678050, 24678051, 88593477, 146511208, 472335975, 534494836,
912985153, 4679307774L, 32164049650L, 32164049651L, 40028394225L, 42678290603L, 44708635679L, 49388550606L, 82693916578L,
94204591914L, 28116440335967L, 4338281769391370L, 4338281769391371L, 21897142587612075L, 35641594208964132L, 35875699062250035L,
1517841543307505039L, 3289582984443187032L, 4498128791164624869L, 4929273885928088826L};
for (int i = 0; i < mas1.length; i++) {
if (mas1[i] == test[i]) {
System.out.println("ОК - " + test[i] + " = " + mas1[i]);
} else {
System.out.println("NO - " + test[i] + " != " + mas1[i]);
}
}
long[] mas2 = getNumbers(0);
System.out.println(Arrays.toString(mas2));
long[] mas3 = getNumbers(1);
System.out.println(Arrays.toString(mas3));
long[] mas4 = getNumbers(370);
System.out.println(Arrays.toString(mas4));
}
}