Задача: 202. Happy Number
Сложность: easy

Напишите алгоритм для определения, является ли число n счастливым
Счастливое число определяется следующим процессом:
Начиная с любого положительного целого числа, замените число суммой квадратов его цифр.
Повторяйте процесс, пока число не станет равным 1 (где оно и останется), или пока оно бесконечно не будет циклически повторяться в цикле, который не включает 1.
Те числа, для которых этот процесс завершается 1, являются счастливыми.
Верните true, если n является счастливым числом, и false, если нет.

Пример:

Input: n = 2
Output: false

👨‍💻 Алгоритм:

1⃣Для заданного числа n определите следующее число в последовательности: используйте операторы деления и взятия остатка для последовательного извлечения цифр из числа, пока не закончатся все цифры. Каждую извлеченную цифру возводите в квадрат и суммируйте полученные значения. Это техника "последовательного извлечения цифр" является полезным инструментом для решения множества задач.

2⃣Отслеживайте цепочку чисел и определяйте, не вошли ли вы в цикл, используя структуру данных HashSet. Каждый раз, генерируя следующее число в цепочке, проверяйте, присутствует ли оно уже в HashSet.

3⃣Если числа нет в HashSet, добавьте его туда. Если число уже есть в HashSet, это означает, что вы находитесь в цикле, и следует вернуть false. HashSet используется вместо Vector, List или Array, потому что проверка присутствия числа в HashSet занимает время O(1), тогда как в других структурах данных это займет время O(n). Правильный выбор структур данных является ключевым элементом решения подобных задач.

😎 Решение:

function getNext($n) {
    $totalSum = 0;
    while ($n > 0) {
        $digit = $n % 10;
        $n = floor($n / 10);
        $totalSum += $digit * $digit;
    }
    return $totalSum;
}

function isHappy($n) {
    $seen = [];
    while ($n != 1 && !in_array($n, $seen)) {
        $seen[] = $n;
        $n = getNext($n);
    }
    return $n == 1;
}
echo isHappy(19) ? "true" : "false";

Ставь 👍 и забирай 📚 Базу знаний