Решение построено исходя из статьи.
Программа высчитывает значение ряда чисел согласно правилу: "любая цифра не меньше предыдущей и не больше последующей". Вычисления начинаются с 1. Цикл прерывается, если очередное число больше N или равно -1.
Для каждого числа рассчитывается степенная сумма. Если набор цифр степенной суммы совпадает с набором цифр текущего числа, то степенная сумма - это число Армстронга.
Что учитывает код:
- Нулевое и отрицательные значения параметра метода getNumbers
Вывод
[1, 2, 3, 4, 5, 6, 7, 8, 9, 153, 370, 371, 407]
memory 317
time = 0
[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, 4679307774, 32164049650, 32164049651, 40028394225, 42678290603, 44708635679, 49388550606, 82693916578, 94204591914, 28116440335967, 4338281769391370, 4338281769391371, 21249285264662860]
memory 18549
time = 23
package com.javarush.task.task20.task2025;
import java.util.*;
/*
Алгоритмы-числа
*/
public class Solution {
public static long[] getNumbers(long N) {
List<Long> resultList = new ArrayList<>();
long currentNumber = 1;
while (currentNumber < N) {
Long curArm = getArmNum(currentNumber);
if (curArm != null) {
resultList.add(curArm);
}
currentNumber = nextNumber(currentNumber);
}
Collections.sort(resultList);
long[] result = new long[resultList.size()];
for (int i = 0; i < resultList.size(); i++) {
result[i] = resultList.get(i);
}
return result;
}
/**
* @return число армстронга - если оно существует в наборе цифр переденного числа
* null - если число армстронга не существует
*/
private static Long getArmNum(long sourceNum) {
Long result = null;
/* получаем список цифр исходного числа */
List<Integer> sourceNumDigits = getNumDigits(sourceNum);
/* считаем степенную сумму */
long powSum = 0;
for (Integer num : sourceNumDigits) {
powSum += Math.pow(num, sourceNumDigits.size());
}
/* получаем список цифр степенной суммы */
List<Integer> powSumDigits = getNumDigits(powSum);
/* сортируем цифры исходного числа и степенной суммы по одному правилу */
Collections.sort(sourceNumDigits);
Collections.sort(powSumDigits);
/* проверяем совпадают ли наборы цифр исходного числа и степенной суммы */
if (sourceNumDigits.toString().equals(powSumDigits.toString())) {
result = powSum;
}
return result;
}
/**
* @return список цифт переденного цисла
*/
private static List<Integer> getNumDigits(long number) {
/* собираем цифры исходного числа */
long ost = 0;
long divideResult = number;
List<Integer> nums = new ArrayList<>();
/* достаем цифры пока число не кончилось */
do {
ost = divideResult % 10;
nums.add((int) ost);
divideResult = divideResult / 10;
} while (divideResult != 0);
return nums;
}
/**
* @param curNumber - текущее число
* @return возвращает следующее за текущим значение из ряда чисел, каждое из которых
* соответсвует правилу: "любая цифра не меньше предыдущей и не больше последующей"
* 1,2,3,4,5,6, ... ,48,49,50,55, ... ,890,899,900,990,999, ... ,89999999999999000,
* 89999999999999900,89999999999999990,89999999999999999,90000000000000000
*/
private static long nextNumber(long curNumber) {
long ost;
long divRes = curNumber;
int por = 0; // число нулей в конце текущего числа
/* подсчитываем число нулей в конце текущего числа */
while (true) {
ost = divRes % 10;
if (ost != 0) {
break;
}
por++;
divRes = divRes / 10;
}
/* если в конце числа нет нулей выполняем простой декремент*/
if (por == 0) {
curNumber++;
} else {
long delta = ost * (long) Math.pow(10, por - 1);
/* если вычисление нового значения ряда не вызовет переполнения, присваиваем новое значение */
if (Long.MAX_VALUE - curNumber >= delta) {
curNumber += delta;
} else { /* иначе присваиваем значение, которое остановит перебор */
curNumber = - 1;
}
}
return curNumber;
}
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 / 100 )));
b = System.currentTimeMillis();
System.out.println("memory " + (Runtime.getRuntime().totalMemory() - Runtime.getRuntime().freeMemory()) / (8 * 1024));
System.out.println("time = " + (b - a) / 1000);
}
}