“This is the second day of my participation in the Gwen Challenge in November. See details: The Last Gwen Challenge in 2021”

202. Happiness number

The title

  • Write an algorithm to determine whether a number n is a happy number.

  • Happiness number is defined as:

  • For a positive integer, replace the number each time with the sum of squares of the numbers at each of its positions.

  • And then you repeat the process until the number is 1, or it could go on forever but it never gets to 1.

  • If you can change it to 1, then that number is happiness.

  • Return true if n is the happy number; If not, return false.

Example 1:

Input: 19 Output: true Description: 12 + 92 = 82 82 + 22 = 68 62 + 82 = 100 1 + 0 + 0 = 1

Example 1:

Input: n = 2 Output: false

Answer key

Ask questions

  • Does the value go out of bounds?
  • When seeking happy number, can appear infinite cycle how to handle?

Analysis of the

  • So let’s say n is 999, and we bisect every digit81 + 81 + 81 = 243And obviously when a number gets big enough, every bisector is going to be smaller than the number itself; So arrays don’t go out of bounds;
  • Limit the number of loops to avoid infinite loops.

solution

  • You can specify a maximum number of cycles and default if the number of cycles is greater than 100nNot happiness number;
  • I’m going to pass every time I evaluate itsetWay toMapIn the object.
  • setBefore you go throughhasWay to determineMapObject if the node exists, if so, out of the loop;
  • And returnn === 1.

Code Implementation 1

var isHappy = function(n) {
  var sum = 0;
  var count = 100;
  while (count >= 0) {
    while(n ! = =0) {
      sum += Math.pow((n % 10),2);
      n = Math.floor(n / 10);
    }
    if (sum === 1) return true;
    count--;
    n = sum;
    sum = 0;
  }
  return false;
};
Copy the code

Code Implementation 2

var isHappy = function(n) {
  if (n === 1) return true;
  const map = new Map(a);var sum = 0;
  while(! map.has(n)) { map.set(n);while (n) {
      sum += Math.pow(n % 10.2);
      n = Math.floor(n / 10);
    }
    if (sum == 1) {
      return true;
    }
    n = sum;
    sum = 0;
  }
  return false;
};
Copy the code

Spatial complexity

Because the space occupied by the Map object in the above code is affected by the linked list, the space complexity is O(N).

Spatial complexity

The time complexity of traversing the list through while in the above code is O(N) affected by the length of the list.

The advanced

Can you solve this problem with O(1) (i.e., constant) memory?

Analysis of the

Case diagram:

  • As you can see from the example figure above, happiness numbers can be converted into linked lists
  • You can use the fast or slow pointerFast, missileThe fast pointer moves two steps at a time, the slow pointer moves one step at a time.
  • Determine whether the linked list has a ring;
  • returnfast === 1

Code implementation

var isHappy = function(n) {
  var slow = n;
  var fast = getNext(n);
  
  while(slow ! = =1&& slow ! == fast) { slow = getNext(slow); fast = getNext(getNext(fast)); }return fast === 1;
};

var getNext = function(n) {
  var sum = 0;
  while (n) {
    sum += Math.pow(n % 10.2);
    n = Math.floor(n / 10);
  }
  return sum;
};
Copy the code