# LeetCode Easy 202. Happy Number

tags: leetcode

問題

• Explore
• Problems

アイデア

与えられた2桁数がhappy numberかどうか返せという問題です．

happy numberとは

• 各桁の2乗の和から出来た数をnext_numとします
  • next_numが1になるときhappy numberです．
  • next_numの各桁の2乗の和が1になるまでこの作業を繰り返します．無限ループにならなければhappy numberです．

今までに出た数を記録するようなデータ構造を使えば良いですね．

解法

• 各桁の2乗の和を得る関数を書きます．
• std::unordered_mapを使って，今までの各桁の2乗の和を保存します．
  • std::vectorやstd::listやstd::arrayにしないのは検索する際の時間計算量とデータ構造に必要な空間計算量が良いからです．
  • 和が今までに出たことがあるならばfalse
  • そうでないならば，1か確認してそうならばtrueを返します．
    • 1でないならば，新しく数字を記録します．

計算量

登場する数字の数が$N$だとします．

• 時間計算量
  • 和を得る関数は$O(1)$
  • std::unordered_mapへのアクセスには$O(\log N)$
  • 全体で$(<現れる数の種類>)$
• 空間計算量
  • $O(<現れる数の種類>)$

C++

class Solution {
public:
  bool isHappy(int n) {
    unordered_map<int, int> mp; // <num, times>
    while (mp.find(n = getNext(n)) == mp.end()) {
      if (n == 1)
        return true;
      mp[n]++;
    }
    return false;
  }
  
private:
  int getNext(int n) {    
    int sum = 0;
    while (n) {
      sum += (n % 10) * (n % 10);
      n /= 10;
    }
    return sum;
  }
};

Python

class Solution:
    def isHappy(self, n: int) -> bool:
        used_nums = {}
        while not used_nums.get(n):
            if n == 1:
                return True
            
            used_nums[n] = True
            n = self.__get_next(n)
        return False
    
    def __get_next(self, n: int) -> int:
        total = 0
        while n != 0:
            total += (n % 10) * (n % 10)
            n //= 10
        return total