Happy Number

Условие

Напишите алгоритм для определения, является ли число “счастливым”.

Счастливое число определяется следующим образом:

• Начните с положительного целого числа.

• Замените число на сумму квадратов его цифр.

• Повторяйте процесс, пока число не станет равным 1 (где оно останется), или оно не начнет бесконечно повторяться в цикле, который не включает 1.

• Числа, для которых этот процесс заканчивается на 1, являются счастливыми числами.

Верните true, если число является счастливым, и false — если нет.

Примеры

Input: n = 19

Output: true

Explanation:

1² + 9² = 82
8² + 2² = 68
6² + 8² = 100
1² + 0² + 0² = 1

Input: n = 2

Output: false

Explanation:

2² = 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 (цикл)

Решение

fun isHappy(n: Int): Boolean {
    // Начальные значения для "медленного" и "быстрого" указателей
    var slow = n
    var fast = getNext(n)

    // Используем технику "быстрого и медленного указателей"
    // Идея: медленный указатель движется на одну итерацию, а быстрый — на две.
    // Если существует цикл, они встретятся, если нет — быстрый указатель достигнет 1.
    while (fast != 1 && slow != fast) {
        // Медленный указатель делает одну итерацию
        slow = getNext(slow)
        // Быстрый указатель делает две итерации
        fast = getNext(getNext(fast))
    }

    // Если быстрый указатель достиг 1, значит число счастливое
    return fast == 1
}

// Функция для получения следующего числа как суммы квадратов цифр текущего числа
private fun getNext(n: Int): Int {
    var sum = 0
    var num = n

    // Проходим по каждой цифре числа
    while (num > 0) {
        // Извлекаем последнюю цифру
        val digit = num % 10
        // Добавляем квадрат этой цифры к сумме
        sum += digit * digit
        // Убираем последнюю цифру из числа
        num /= 10
    }

    // Возвращаем сумму квадратов цифр
    return sum
}

Временная сложность

O(log n), где n — начальное число, так как на каждом шаге количество цифр в числе уменьшается.

Пространственная сложность

O(log n), для хранения значений в процессе итераций.