Welcome to Subscribe On Youtube
Question
Formatted question description: https://leetcode.ca/all/202.html
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
Algorithm
The example 19 given in the title is a happy number, so let’s look at a situation that is not a happy number. For example, the number 11
has the following calculation process:
1^2 + 1^2 = 2 2^2 = 4 4^2 = 16 1^2 + 6^2 = 37 3^2 + 7^2 = 58 5^2 + 8^2 = 89 8^2 + 9^2 = 145 1^2 + 4^2 + 5^2 = 42 4^2 + 2^2 = 20 2^2 + 0^2 = 4
At the end of the calculation, the number 4 appears again, then the following numbers will repeat the previous order. This cycle does not contain 1, then the number 11 is not a happy number. After discovering the pattern, we can consider how to use code it.
Use HashSet to record all the numbers that have appeared, and then every time a new number appears, look for it in HashSet to see if it exists,
- if it does not exist, add it to the table,
- if it exists, jump out of the loop, and determine whether the number is 1,
- if it is 1. Return true,
- return false if not 1
Code
-
class Solution { public boolean isHappy(int n) { HashSet<Integer> set = new HashSet<Integer>(); while (!set.contains(n)) { set.add(n); n = getSum(n); if (n == 1) { return true; } } return false; } public int getSum(int current) { int sum = 0; while (current > 0) { sum += Math.pow(current % 10, 2); current /= 10; } return sum; } } class Solution_iteration { public boolean isHappy(int n) { HashSet<Integer> st = new HashSet<Integer>(); while (n != 1) { int sum = 0; while (n > 0) { sum += (n % 10) * (n % 10); n /= 10; } n = sum; if (st.contains(n)) { break; } st.add(n); } return n == 1; } } // if find 4 then unhappy class Solution_math { public boolean isHappy(int n) { while (n != 1 && n != 4) { int sum = 0; while (n > 0) { sum += (n % 10) * (n % 10); n /= 10; } n = sum; } return n == 1; } } } ############ class Solution { public boolean isHappy(int n) { int slow = n, fast = next(n); while (slow != fast) { slow = next(slow); fast = next(next(fast)); } return slow == 1; } private int next(int x) { int y = 0; for (; x > 0; x /= 10) { y += (x % 10) * (x % 10); } return y; } }
-
// OJ: https://leetcode.com/problems/happy-number/ // Time: O(1) // Space: O(1) class Solution { public: bool isHappy(int n) { unordered_set<int> s; while (n != 1 && !s.count(n)) { s.insert(n); int next = 0; while (n) { next += pow(n % 10, 2); n /= 10; } n = next; } return n == 1; } };
-
class Solution: def isHappy(self, n: int) -> bool: def next(x): y = 0 while x: x, v = divmod(x, 10) y += v * v return y slow, fast = n, next(n) while slow != fast: slow, fast = next(slow), next(next(fast)) return slow == 1 ############ class Solution(object): def isHappy(self, n): """ :type n: int :rtype: bool """ record = {} sq_sum = 0 while n != 1: sq_sum = 0 sub_num = n while sub_num > 0: sq_sum += (sub_num % 10) * (sub_num % 10) sub_num /= 10 if sq_sum in record: return False else: record[sq_sum] = 1 n = sq_sum return True
-
func isHappy(n int) bool { next := func(x int) (y int) { for ; x > 0; x /= 10 { y += (x % 10) * (x % 10) } return } slow, fast := n, next(n) for slow != fast { slow = next(slow) fast = next(next(fast)) } return slow == 1 }
-
function isHappy(n: number): boolean { const getNext = (n: number) => { let res = 0; while (n !== 0) { res += (n % 10) ** 2; n = Math.floor(n / 10); } return res; }; let slow = n; let fast = getNext(n); while (slow !== fast) { slow = getNext(slow); fast = getNext(getNext(fast)); } return fast === 1; }
-
impl Solution { pub fn is_happy(n: i32) -> bool { let get_next = |mut n: i32| { let mut res = 0; while n != 0 { res += (n % 10).pow(2); n /= 10; } res }; let mut slow = n; let mut fast = get_next(n); while slow != fast { slow = get_next(slow); fast = get_next(get_next(fast)); } slow == 1 } }