Happy Number
EasyThe problem
Start with n and replace it with the sum of the squares of its digits, over and over. If this ever reaches 1, n is a happy number. If it instead loops forever without reaching 1, it is not. Return true if n is happy.
- Example 1Input: n = 19Output: true
1² + 9² = 82, then 8² + 2² = 68, then 6² + 8² = 100, then 1² + 0² + 0² = 1.
- Example 2Input: n = 2Output: false
It goes 4, 16, 37, 58, 89, 145, 42, 20, 4 and then repeats without ever reaching 1.
- 1 ≤ n ≤ 2,147,483,647
Write it in Go. Try for about 20 minutes on paper first, then open one hint at a time.
Try it here
Write Go. Common packages like fmt and sort are imported for you. Keep the function name and inputs the same.
Hints, one at a time
Nudge
The sequence either reaches 1 or loops forever. Where have you seen cycle detection?
The idea
Repeat sum-of-squares-of-digits; stop at 1 (happy) or when a value repeats (use a set or slow/fast pointers).
Target: O(log n) per step
Go function shape
func isHappy(n int) boolReference solution
Tested with go test. Try it yourself first, then compare.
// IsHappy: sum the squares of the digits repeatedly. Reaching 1 means happy;
// the sequence is a linked list, so a repeat means a cycle (detected with slow and fast pointers).
func IsHappy(n int) bool {
step := func(x int) int {
sum := 0
for ; x > 0; x /= 10 {
d := x % 10
sum += d * d
}
return sum
}
slow, fast := n, step(n)
for fast != 1 && slow != fast {
slow = step(slow)
fast = step(step(fast))
}
return fast == 1
}