Problem

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:

1
2
3
4
5
6
7
8
Input: n = 19
Output: true
Explanation:
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1

Example 2:

1
2
3
Input: n = 2
Output: false

Constraints:

  • 1 <= n <= 2^31 - 1

Solve

沒甚麼難度的一題

要想辦法將非happy number的挑出來，所以做了一個memo，當經過迴圈運算後，數字又變成memo裏頭數字時，代表不可能是happy number

法1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def isHappy(self, n: int) -> bool:
        memo = {}
        
        while n > 0 and n not in memo:
            n2 = 0
            n_s = str(n)

            for i in range(len(n_s)):
                n2 += int(n_s[i])*int(n_s[i])

            if n2 == 1 :
                return True
            memo[n] = False
            
            n = n2
        
        return False

memo 可以改成 set()，不用用dict

運算其實可以不用轉變字串

用除於10的餘數來做也是可以

但這邊就不寫了

法2 Two pointer!!

一開始想不到可以用這樣的方法

two pointer 這邊建立兩個pointer 一個快 一個慢

當兩個pointer 同樣時停止

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def isHappy(self, n: int) -> bool:
        p1,p2 = n,n
        def f_sqr(n):
            total = 0
            while n > 0:
                total += (n%10) * (n%10)
                n //= 10
            
            return total

        while True:
            p1 = f_sqr(p1)
            p2 = f_sqr(f_sqr(p2))

            if p1 == p2:
                break
        
        return p1 == 1