“This is the first day of my participation in the First Challenge 2022. For details: First Challenge 2022”

3 minutes a day, fast learning algorithm

Algorithmic Fitness Program. – Week one

Subject address – 202. Happiness number

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 if n is the happiness numbertrue; If no, returnfalse 。

19 -> 82 -> 68 -> 100 -> 1

1 squared plus 9 squared is 82

8 squared plus 2 squared is 68

6 squared plus 8 squared is 100

1 squared plus 0 squared plus 0 squared is 1

Train of thought

  • The problem can be converted to, say, whether or not a linked list has rings.
  • If you go through a node and it’s 1, you have no loop, you have a happy number.
  • If you iterate over repeated node values, you have a ring, not a happy number.

thinking

Q: Will the numbers get bigger?

digits The maximum The next number
1 9 81
2 99 162
3 999 243
4 9999 324

A: X -> x^2 when the maximum, 199999999… 999,81 times 9 plus 1 is 730, so it’s going to be at most 730, and it’s not going to get any bigger

Background:

In c++, integers range from -2 147 483 648 to +2 147 483 647, so the largest number that matches the above is 1 999 999 999. The sum of squares of each of these integers is 81 * 9 + 1 = 730, meaning that the maximum sum of squares is 730, with a maximum of 730 nodes.

answer

The set determines whether there is a ring

Keep searching for the next happiness number and record it in set. If the number is found to be repeated, it is not a happiness number, and vice versa.

  • If it is not in the Set, it should be added
  • If in the Set, the statement has already started the loop, then it is not a happy number

The illustration

// Get the next happiness number
const getNext = n= > {
  let total = 0
  while(n > 0) {
    total += Math.pow(n % 10.2)
    n = ~~(n / 10)}return total
}


const isHappy = n= > {
  const visited = new Set(a)while(n ! = =1&& getNext(n) ! = =1) {
    // If repeated, it is not happiness number
    if (visited.has(n)) {
      return false
    }

    visited.add(n)
    n = getNext(n)
  }
  
  // When you arrive here, you do not repeat
  return true
}
Copy the code

Check if element is in Set: O(1)

Time complexity: O(logn)

How fast a pointer

The fast pointer takes one more step than the slow pointer each time. If there are rings, they will definitely meet. If there are no rings, they are happy numbers.

The illustration

const getNext = n= > String(n).split(' ').reduce((pre, cur) = > pre + Math.pow(cur, 2), 0)

const isHappy = n= > {
  let fast = n
  let slow = n

  while(fast ! = =1&& getNext(fast) ! = =1) {
    fast = getNext(getNext(fast))
    slow = getNext(slow)
    // If you reach 1, you are happy
    if (fast === 1) {
      return true
    }

    if (fast === slow) {
      return false}}return true
}
Copy the code