【LeetCode】202. Happy Number 解答・解説【Python】

問題
1. 原文
2. 内容
解答
1. 解答1：Python
2. 解答2：Python, 英語コメント
メモ・参考・感想

問題

原文

Write an algorithm to determine if a number n is happy.

A happy number is a number defined by the following process:

Starting with any positive integer, replace the number by the sum of the squares of its digits.

Repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1.

Those numbers for which this process ends in 1 are happy.

Return true if n is a happy number, and false if not.

Example 1:

Input: n = 19 Output: true Explanation: 12 + 92 = 82 82 + 22 = 68 62 + 82 = 100 12 + 02 + 02 = 1

1
2
3
4
5
6
7

Input: n = 19
Output: true
Explanation:
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1

Example 2:

Input: n = 2 Output: false

1
2

Input: n = 2
Output: false

Constraints:

1 <= n <= 2³¹ - 1

内容

数字nがhappyであるかを判定するアルゴリズムを書いてください。

happy numberは以下のプロセスによって定義されます。

・正の整数を各桁の2乗の合計値に置き換える

・数字が1になるか、1以外の数字で無限ループに入るまで繰り返す

・最終的に1になったらhappy number

happy numberならTrue、そうでなければFalseを返してください。

※正しくない可能性があります。

解答

解答1：Python

#整数nから各桁の2乗の合計値を求める
#求めた合計値から、さらに各桁の2乗の合計値を求める
#上記を繰り返して1になったらハッピーナンバー

class Solution:
    def isHappy(self, n: int) -> bool:   
        #1度処理を実行した数字を格納する変数。無限ループ防止用            
        visited = set()
        #nが1以外であり、nがvisitedにない限り繰り返す
        while n != 1 and n not in visited:
            #visitedにnを追加
            visited.add(n)
            #temp_nを毎回0にする。
            temp_n = 0
            #nが0よりも大きい限り繰り返す
            while n > 0:
                #n%10はnを10で割った余りを求めている→必ず下一桁を取得できる
                #pow(n%10, 2)で、nの下一桁の2乗を求めている
                #temp_nに、上記の処理で求めた値を加える
                temp_n += pow(n%10, 2)
                #nを10で割り、下一桁の数字をnから外す。2進数で言うビットシフトと同じ操作に見える
                #内側のwhileの最後は、nは0になり、temp_nは各桁の2乗の合計値になっている
                n //= 10
            #nにtemp_nの値を代入
            n = temp_n
        return n == 1

#整数nから各桁の2乗の合計値を求める

#求めた合計値から、さらに各桁の2乗の合計値を求める

#上記を繰り返して1になったらハッピーナンバー

class Solution:

def isHappy(self, n: int) -> bool:

#1度処理を実行した数字を格納する変数。無限ループ防止用

visited = set()

#nが1以外であり、nがvisitedにない限り繰り返す

while n != 1 and n not in visited:

#visitedにnを追加

visited.add(n)

#temp_nを毎回0にする。

temp_n = 0

#nが0よりも大きい限り繰り返す

while n > 0:

#n%10はnを10で割った余りを求めている→必ず下一桁を取得できる

#pow(n%10, 2)で、nの下一桁の2乗を求めている

#temp_nに、上記の処理で求めた値を加える

temp_n += pow(n%10, 2)

#nを10で割り、下一桁の数字をnから外す。2進数で言うビットシフトと同じ操作に見える

#内側のwhileの最後は、nは0になり、temp_nは各桁の2乗の合計値になっている

n //= 10

#nにtemp_nの値を代入

n = temp_n

return n == 1

・1つ目のwhile文では、nが1以外であり、まだ出現していない数なら処理を繰り返している。

・temp_nはnの各桁の二乗の合計を保持する変数。

・2つ目のwhile文が終了するまでは保持しておき、1つ目のwhile文で次のループに移った時に0で初期化する。こうしないと、前回のnの合計数値をもちこしてしまう。

・出現した数字をvisitedに加えて記録しておき、1つ目のwhile文の次回のループを始める前に判定を行う。

・2つ目のwhile文の内部では、各桁の二乗の合計値を求めている。

・nの数字の1桁目を、%を使って求め、これを二乗して変数に加える。

・nは//を使って1桁目を除外している

解答2：Python, 英語コメント

#Input number is n.
#We need to return True if sum of squares of each digit is 1.
#In any other case, we need to return False.

class Solution:
    def isHappy(self, n: int) -> bool:
        #keep number once occured in loop.
        occured_number = set()
        #do loop while n is not 1
        while n!=1:
            #Initialize a variable to store the sum of squares of each digit in every loop
            sum_of_squares = 0
            #If n has cccurred once, return False.
            if n in occured_number:
                return False
            
            #Add n to occured_number variable.
            occured_number.add(n)

            #Calculate the sum of squares of each digit
            #
            while n>0:
                #obtain one's place number
                last_digit = n%10
                #exclude first digit from n
                n = n // 10
                #Add square of last_digit variable
                sum_of_squares += last_digit**2
            #Assign sum_of_squares to n
            n = sum_of_squares
        #if n is 1, escape loop and return True
        return True

#Input number is n.

#We need to return True if sum of squares of each digit is 1.

#In any other case, we need to return False.

class Solution:

def isHappy(self, n: int) -> bool:

#keep number once occured in loop.

occured_number = set()

#do loop while n is not 1

while n!=1:

#Initialize a variable to store the sum of squares of each digit in every loop

sum_of_squares = 0

#If n has cccurred once, return False.

if n in occured_number:

return False

#Add n to occured_number variable.

occured_number.add(n)

#Calculate the sum of squares of each digit

while n>0:

#obtain one's place number

last_digit = n%10

#exclude first digit from n

n = n // 10

#Add square of last_digit variable

sum_of_squares += last_digit**2

#Assign sum_of_squares to n

n = sum_of_squares

#if n is 1, escape loop and return True

return True

解き方は解答1と同じ。

英語での練習の表現用

メモ・参考・感想

■メモ

今更ながら、かつ初歩的だけど「n//=10」の操作で2進数のビットシフトのイメージをつかんだかもしれない。

・2進数のビットシフトを行うと、桁が1つ下がり、10進数では半分の数字になる。

・10進数を10で割ると、桁が1つ下がり、10進数で10分の1の数字になる。

前：637. Average of Levels in Binary Tree

次：1523. Count Odd Numbers in an Interval Range

解答前に知っておくと役に立つかもしれない情報

LeeetCodeの問題をアルゴリズムとデータ構造による分類

LeetCode 解答・解説記事一覧