Happy Number

The problem

Start with the positive whole number n and replace it, again and again, with the sum of the squares of its digits: 19 becomes 1 × 1 + 9 × 9 = 82. A number is happy if this chain of values reaches 1, where it then stays. The number 1 itself is happy. If the chain never reaches 1, it goes round the same values forever. Return true if n is happy and false if it is not.

What to write

function solve(n: number): boolean

Input
n = 19

Output
true

Input
n = 2

Output
false

Constraints

Positive integer n ≤ 2,147,483,647.

Hints

Each hint gives away a little more. Open one only when you need it.

1. Hint 1: Use the constraints

   n can be as large as 2,147,483,647, which has ten digits. But a digit is at most 9, so one step turns any allowed number into at most 10 × 81 = 810. After the first step every value is small, so the chain has only a limited stock of values to visit.

2. Hint 2: Ask a smaller question

   Follow n = 2 by hand: 2, 4, 16, 37 and so on. Keep going until you are sure that this chain will never reach 1. What did you see that made you sure? And what did you have to look back at to see it?

3. Hint 3: Name the pattern

   Each value fully decides the next one. So when a value other than 1 turns up a second time, everything after it repeats too: the chain is caught in a cycle, a loop of values, and never reaches 1. Remember every value you pass and ask "have I seen this one before?" before going on. That is hash set membership. Read the lesson on hash set membership.

4. Hint 4: State the invariant

   Before each step, the set holds every value the chain has passed, and none of them is 1. If the current value is 1, the answer is true. If the current value is already in the set, the chain has closed a cycle that does not contain 1, so the answer is false.

5. Hint 5: Sketch the pseudocode

   seen = empty set. While n is not 1 and not in seen: add n to seen; total = 0; while n is above 0, add the square of its last digit (the remainder of n divided by 10) to total, then divide n by 10 and drop the remainder; set n to total. Return whether n is 1.

Solution

From here on the page gives the method away. If you are still solving, go back to the hints.

Approach

Replace n with its digit-square sum until it reaches 1 or repeats. A Set detects a cycle, after which reaching 1 is impossible.

The slow way

Keep replacing the number with the sum of the squares of its digits until it reaches 1, then answer true. For a happy number that works. For any other number the loop never ends: 2 goes round 4, 16, 37, 58, 89, 145, 42, 20 and back to 4 forever, and the program never gets to answer false.

The insight

The next value depends only on the current one. So if a value other than 1 ever comes back, the chain from there on is an exact replay: it is caught in a cycle, a loop of values that repeats forever, and will never reach 1. Remembering the values already passed turns "this never ends" into something you can see happen: a value you have met before.

Step by step

1. A set remembers every value the chain has passed. A set answers "have I seen this value?" in about one step, however many values it holds. Nothing has been passed yet, so it starts empty.
2. Go on until the value is 1 or is one that was seen before. Those are the only two ways the chain can settle. At 1 it stays at 1, because 1 squared is 1. At a repeated value it goes round the same cycle again.
3. Remember the current value. The value has to go into the set before the chain moves on, or its return could not be noticed later. The loop tested it first, so it never finds itself.
4. Add up the squares of its digits, taking the last digit each time. The remainder after dividing by 10 is the last digit. Dividing by 10 and dropping the remainder removes that digit, so the next one becomes the last. The order does not change a sum.
5. The sum becomes the next value of the chain. That is the rule of the problem: each value is replaced by the sum of the squares of its digits. The next round tests this new value.
6. The number is happy exactly when the chain stopped at 1. The loop ends only at 1 or at a value seen before. A repeated value means a cycle of values that were all tested and were not 1.

The same numbered steps are the comments in each solution.

function solve(n) {
  // 1. A set remembers every value the chain has passed
  const seen = new Set();
  // 2. Go on until the value is 1 or is one that was seen before
  while (n !== 1 && !seen.has(n)) {
    // 3. Remember the current value
    seen.add(n);
    // 4. Add up the squares of its digits, taking the last digit each time
    let sum = 0;
    while (n) {
      sum += (n % 10) ** 2;
      n = Math.floor(n / 10);
    }
    // 5. The sum becomes the next value of the chain
    n = sum;
  }
  // 6. The number is happy exactly when the chain stopped at 1
  return n === 1;
}

function solve(n: number): boolean {
  // 1. A set remembers every value the chain has passed
  const seen = new Set();
  // 2. Go on until the value is 1 or is one that was seen before
  while (n !== 1 && !seen.has(n)) {
    // 3. Remember the current value
    seen.add(n);
    // 4. Add up the squares of its digits, taking the last digit each time
    let sum = 0;
    while (n) {
      sum += (n % 10) ** 2;
      n = Math.floor(n / 10);
    }
    // 5. The sum becomes the next value of the chain
    n = sum;
  }
  // 6. The number is happy exactly when the chain stopped at 1
  return n === 1;
}

def solve(n):
    # 1. A set remembers every value the chain has passed
    seen = set()
    # 2. Go on until the value is 1 or is one that was seen before
    while n != 1 and n not in seen:
        # 3. Remember the current value
        seen.add(n)
        # 4. Add up the squares of its digits, taking the last digit each time
        total = 0
        while n:
            total += (n % 10) ** 2
            n //= 10
        # 5. The sum becomes the next value of the chain
        n = total
    # 6. The number is happy exactly when the chain stopped at 1
    return n == 1

Example 2, traced

Input
n = 2

Output
false

Why it works

After the first step no value is above 810, so the chain cannot keep meeting new values: sooner or later it reaches 1 or repeats a value. The loop stops at whichever happens first. A repeat means a cycle made only of values that were tested and were not 1, so the chain can never reach 1, and false is right.

Time and space

Time O(s × d), s visited states and d digits, extra space O(s). The loop runs once for each value the chain passes before it stops: s rounds. A round takes one step per digit, at most d, so the time is O(s × d). The set holds those s values: O(s) space. In the tests here s is never above 16.

n and m are input sizes, h is a tree's height, V and E are a graph's vertices and edges. The bounds describe this reference solution.

Watch out

• Remember every value, not only the starting one. The chain from 2 never returns to 2: it enters the cycle at 4. A loop that waits for 2 to come back never ends.
• Start the sum at 0 again for every new value. With one running sum kept across the rounds, the value only grows: from 19 it goes 82, 150, 176 and on, never back to 1, and the loop never ends.
• Drop the remainder when you divide by 10. With plain division 19 becomes 1.9 instead of 1, so the next "digit" is 1.9, and the first sum for 19 comes out near 84.6 instead of 82.

Pattern

Hash set membership. Builds on Contains Duplicate and Linked List Cycle.

Keep going