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
Example 2:
Input: n = 2 Output: false
Constraints:
1 <= n <= 231 - 1
Solution: Simulation
We can use a hasthable to store all the number we generated so far.
Time complexity: O(L)
Space complexity: O(L)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
// Author: Huahua class Solution { public: bool isHappy(int n) { auto getNext = [](int x) -> int { int ans = 0; while (x) { ans += (x % 10) * (x % 10); x /= 10; } return ans; }; unordered_set<int> s; while (n != 1) { if (!s.insert(n).second) return false; n = getNext(n); } return true; } }; |
Optimization: Space reduction
Since the number sequence always has a cycle, we can use slow / fast pointers to detect the cycle without using a hastable.
Time complexity: O(L)
Space complexity: O(1)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
// Author: Huahua class Solution { public: bool isHappy(int n) { auto getNext = [](int x) -> int { int ans = 0; while (x) { ans += (x % 10) * (x % 10); x /= 10; } return ans; }; int slow = n; int fast = getNext(n); do { slow = getNext(slow); fast = getNext(getNext(fast)); } while (slow != fast); return slow == 1; } }; |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Paypal
Venmo
huahualeetcode
huahualeetcode
微信打赏
Be First to Comment