---

Условие задачи

Число называется счастливым, если последовательная замена числа суммой квадратов его цифр в итоге приводит к 1. Для несчастливого числа процесс никогда не достигает 1, а попадает в цикл, который не содержит 1.

Определите, является ли заданное положительное число счастливым.

Пример 1:

Вход: 23
Выход: true

Число 23 счастливое: \(2^2 + 3^2 = 13\), затем \(1^2 + 3^2 = 10\) и \(1^2 + 0^2 = 1\).

Пример 2:

Вход: 12
Выход: false

Для числа 12 последовательность попадает в цикл:

89 -> 145 -> 42 -> 20 -> 4 -> 16 -> 37 -> 58 -> 89

Решение

Процесс всегда заканчивается циклом: счастливое число зацикливается на 1, а несчастливое — на другой последовательности чисел. Поэтому применим быстрый и медленный указатели. Медленный указатель на каждом шаге один раз вычисляет сумму квадратов цифр, а быстрый — два раза. После их встречи достаточно проверить, равно ли найденное значение 1.

Код

Вот как будет выглядеть наш алгоритм:

package main

import "fmt"

func isHappy(number int) bool {
	slow, fast := number, number

	for {
		slow = squareDigitSum(slow)
		fast = squareDigitSum(squareDigitSum(fast))

		if slow == fast {
			break
		}
	}

	return slow == 1
}

func squareDigitSum(number int) int {
	sum := 0

	for number > 0 {
		digit := number % 10
		sum += digit * digit
		number /= 10
	}

	return sum
}

func main() {
	fmt.Println(isHappy(23))
	fmt.Println(isHappy(12))
}

Вывод:

true
false

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

После первой замены значение не превосходит 81 умножить на количество цифр исходного числа. Поэтому временная сложность алгоритма равна \(O(\log N)\).

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

Алгоритм использует постоянный объём дополнительной памяти, поэтому пространственная сложность равна \(O(1)\).

---