LeetCode Notes: Happy Number

#leetcode

Question

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

Analysis:

There are two situations

  1. Loop the sum of squares to get the result 1, which is true
  2. Infinite loop, no result 1 is obtained. At this time, use the fast and slow pointers to determine whether there are two pointers meeting to determine whether it is in an infinite loop

Code:

/**

  * @param {number} n
  * @return {boolean}
  */
var isHappy = function(n) {

     let after = n // current value
     let forward = nextNum(n) // step forward

     // Exit the loop in the following two cases
     // forward == after: fast and slow pointers meet
     // forward == 1: got the result 1
     while(forward != after && forward != 1){
         after = nextNum(after) // Slow pointer goes one step forward
         forward = nextNum(nextNum(forward)) // Fast pointer goes two steps forward
     }

     // return result
     return forward == 1

     // Get the next number, that is, the sum of the squares of the numbers at each position
     function nextNum(n){
         return (n +'').split('').map(a => a ** 2).reduce((x,y)=> x + y)
     }

};

Reference

Comments