202. Happy Number

Difficulty:
Related Topics:
Similar Questions:

Problem

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

Solution 1

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

  if (n < 1) return false;

  while (n !== 1 && !map[n]) {
    map[n] = true;
    tmp = 0;

    while (n > 0) {
      tmp += Math.pow(n % 10, 2);
      n = Math.floor(n / 10);
    }

    n = tmp;
  }

  return n === 1;
};

Explain:

nope.

Complexity:

Solution 2

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

  if (n < 1) return false;

  do {
    slow = getsumsquare(slow);
    fast = getsumsquare(getsumsquare(fast));
  } while (slow !== fast);

  return slow === 1;
};

var getsumsquare = function (n) {
  var sum = 0;
  var tmp = 0;

  while (n > 0) {
    tmp = n % 10;
    sum += tmp * tmp;
    n = Math.floor(n / 10);
  }

  return sum;
};

Explain:

两种情况:有 1 和 循环。

循环的时候,在一个圈里,两人在相同的地方同时出发,一个人每次走一步,另一个人每次走两步,他们肯定会再相遇。

1 的时候,两人都会停留在 1

Complexity: