Решение задачи 202 “Счастливые числа” с https://leetcode.com

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

Счастливые числа - эта числа, которые можно проверить следующим алгоритмом: это число положительное, складываем квадраты всех его цифр, повторяем процесс пока не сумма не станет равной 1 ( если алгоритм зациклился - числа не являются счастливыми ).

Пример

1
2
3
4
5
6
7

Input: 19
Output: true
Объяснение: 
1^2 + 9^2 = 82
8^2 + 2^2 = 68
6^2 + 8^2 = 100
1^2 + 0^2 + 0^2 = 1

Решение

Идея решения - проверяем в лоб.

Для этого заводим коллекцию, где ключом будем число ( сумма квадратов цифр числа n ) - значение всегда true. Запускаем цикл с условием n!=1 ( n не равен единице ). в цикле считаем сумму квадратов цифр.

Потом проверяем - есть ли эта сумма в ранне созданное коллекции:

• Если эта сумма уже встречалась, значит мы зациклились и можно число не является счастливым.
• Если суммы нет в коллекции - добавляем её в коллецию.

Если мы вышли из цикла - значит сумма квадратов стала равно единицы и изначальное число было счастливым.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

func isHappy(n int) bool {
    if n <=0 {
        return false
    }
    used := make(map[int]bool)
    used[n] = true
    for n!=1 {
        k:= n
        sum := 0
        for k>0 {
            w:=k%10
            k = k/10
            sum +=w*w
        }
        if _, ok := used[sum]; ok {
            return false
        }
        used[sum] = true
        
        n = sum
    }
    
    return true
}