パターン1 7 → 49 → 97 → 130 → 10 → 1
パターン2 2 → 4 → 16 → 37 → 30 → 9 → 81 → 65 → 61 → 37
Algorithm
-
number n の次の数が何かを調べる
-
cycle に入ったかを調べる。
-
の調べ方 19 → 1^2 + 9^2 = 82
変数 output に 0 を代入し、 while で n がある間
n = 19 の場合、
1の位を取得 19 % 10 = 9
9 ** 2 = 81
output += 81
10の位を取得 n = 19 // 10 = 1
while で上記と同様の処理。 このループで n = 1 // 10 = 0
となり、ループを抜ける。
- cycle に入ったかの調べ方。 HashSet を使い、すでに訪れた数かを調べる。 すでに訪れた場合、 cycle に入ったことがわかるので、 その時点で False を返す。 もし訪れてなければ、HashSet に追加。 n == 1 となれば True を返す。
class Solution:
def isHappy(self, n: int) -> bool:
visit = set()
while n not in visit:
visit.add(n)
n = self.sum_of_squares(n)
if n == 1:
return True
return False
def sum_of_squares(self, n: int) -> int:
output = 0
while n:
digit = n % 10
digit = digit ** 2
output += digit
n = n // 10
return output