UniLecs #Task. Happy number
Задача: Счастливое число — это число, определённое следующим процессом: начиная с любого положительного целого числа, мы заменяем это число суммой квадратов его цифр в десятичной системе счисления и повторяем данный процесс, пока число либо не станет равно 1 (где весь процесс остановится), или попадёт в бесконечный цикл, не содержащий 1. Числа, для которых данный процесс заканчивается единицей, называются счастливыми числами, в то время как те, для которых процесс не заканчивается единицей, считаются несчастливыми числами.
Напишите функцию, которая определяла бы является ли заданное число N счастливым.
Входные данные: N — натуральное число от 1 до 1000.
Вывод: true/false — является ли число счастливым.
Примеры
- N = 19
1² + 9² = 82
8² + 2² = 68
6² + 8² = 100
1² + 0² + 0² = 1.
Output: true - N = 2;
Output: false
Разбор
Число не будет счастливым числом, если оно зацикливается в своей последовательности, т.е. на iй итерации мы встречаем число, которое уже было на одной из предыдущих итераций.
Поэтому для нашего алгоритма, мы можем использовать структуру HashSet, где будем хранить набор, и если мы снова встретим элемент, который уже есть в HashSet, значит мы попали в цикл и число не может быть счастливым.
Например, N = 4;
4² -> 16 -> 1² + 6² -> 37 -> 3² + 7² -> 58 -> 5² + 8² -> 89 -> 8² + 9² -> 145 -> 1² + 4² + 5² -> 42 -> 4² + 2² -> 20 -> 2² + 0 -> 4.
Значит, N = 4 — не является счастливым числом.
Почему последовательность для несчастливых чисел будет зацикливаться, а не расти со временем?! Достаточно посчитать предельные значения для чисел из 2х, 3х, 4х цифр.
- 99 –> 81 + 81 = 162
- 999 –> 81 + 81 + 81 = 243
- 9999 –> 81 + 81 + 81 + 81 = 324
- 9999999999 –> 10 * 81 = 810
- для числа из 20 девяток → 20 * 81 = 1620
Даже для числа из 20 девяток следующих числом в последовательности будет всего 4х значное число. А для 4х значного числа след.число будет уже 3х значное. То есть последовательность ограничена конечным кол-вом чисел. И если мы не встретим 1, то на очередной итерации мы встретим число, которое уже было в последовательности.
Реализация
https://gist.github.com/unilecs/cb0f7d3e1b718a206482675a39d1dea9
