You get a whole number n. Return true if n is happy, and false if it is not.
To find out, square each digit and add up the squares. That total is your next number.
Do the same with the next number, and keep going. If you get to 1, n is happy. From 1 you only get 1 again.
Otherwise the numbers come back around in a loop without 1. Then n is not happy.
Example 1:
Input: n = 23 Output: true Explanation: 2² + 3² = 4 + 9 = 13. 1² + 3² = 1 + 9 = 10. 1² + 0² = 1 + 0 = 1. We got to 1, so 23 is happy.
Example 2:
Input: n = 4 Output: false Explanation: 4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4. The chain is back at 4, so these 8 numbers repeat forever. None of them is 1.
Example 3:
Input: n = 1 Output: true Explanation: n is already 1.
Constraints:
nis a whole number from 1 to 2,147,483,647.- That top value is 231 − 1.
Your solution should run in O(log n) time and use O(1) extra space.
Write the numbers down in order. They form a chain, and each number decides the next one. So once a number shows up a second time, the chain loops forever.
You could keep every number you see in a set. You can also do it with no memory at all. Walk the chain with two runners: a slow one moves one number at a time, a fast one moves two. If the chain loops, the fast runner catches up with the slow one. If it reaches 1, the fast runner gets there first.
The first move looks at each digit of
n, and n has about log10 n digits: O(log n) time.After that move every number is at most 810 (ten digits of 9), so the rest of the walk takes a small, fixed number of moves.
The two runners are just two numbers, so the extra space is O(1).
Free plan: 30 tutor messages. Premium is unlimited.
Saved
Ctrl + Enter to check
