Leetcode - Largest Number At Least Twice of Others
Leetcode - Move Zeroes

Leetcode - Happy Number

violet posted @ Apr 03, 2020 01:11:04 AM in 算法 with tags Algorithm Golang hash , 211 阅读

https://leetcode.com/problems/happy-number/

Write an algorithm to determine if a number 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, and 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 numbers.

Example: 

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

 

There are several conditions in the end.

1. sum equal to 1

2. sum repeat in a loop

3. sum goes infinity

Use a hash to track every round of sum and see whether it occurs before, if so, return false

func isHappy(n int) bool {
    hash := map[int]bool{}
    for n != 1 && !hash[n] {
        hash[n] = true
        n = getNext(n)
    }
    return n == 1
}

func getNext(n int) int {
    sum := 0
    for n > 0 {
        d := n%10
        n /= 10
        sum += d*d
    }
    return sum
}

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter