Happy Number Problem

Tagged: Hash Table, Math, Two Pointers

Problem#

A number is said to be happy if when it is replaced by the sum of the square of its digits, it will eventually reach 1. For example, 13 is a happy number because 1² + 3² = 10, then 1² + 0² = 1. However, 2 is not a happy number because 2² = 4, 4² = 16, 1² + 6² = 37, and eventually will cycle back to 4 without ever reaching 1.

Below are some of the examples:

Input: 19
Output: true
Explanation: 19 -> 82 -> 68 -> 100 -> 1

Input: 2
Output: false
Explanation: 2 -> 4 -> 16 -> 37 -> 58 -> 89 -> 145 -> 42 -> 20 -> 4

Constraints: 1 <= n <= 231 - 1

Solution#

To solve this kind of problem, it’s better to write down some of the examples. Based on samples above, we know that there are two possibilities that might happen.
First, the number will eventually reach 1.
Second, the number will eventually enter the loop and cycle back to its earlier number to form a loop.

However, there might be Third case where the number will keep increasing and reaching infinity. Fortunately, this will never happen.
Please notice below table where we enumerate the largest possible number for certain amount of digits and its next number.

Even for a largest number that has 13 digits, the next number (1053) only has 4 digits then the next one will be lower than 324 since the next number of the largest 4 digits number (9999) will be 324 only.
The next one is guaranteed to be lower than 243 because the next number after 999 (the largest number with 3 digits) is 243.
From this, we can infer how quickly total digits will dwindle from a very large number to the next. Once the number of digits has decreased to 3 digit, it will never go up and stuck with a number below 243.
Therefore, it will either cycle or end up with 1, hence there are only two cases we need to handle.

1. Finding the next number
2. Detect whether it has been found previously which means a cycle is detected.

HashSet#

To solve the first case above, we need to to apply modulus operation to get the last digit of a number, then the number is divided by 10 so that after squaring the remainder (last digit), the last digit can be removed from the original number.
For the second case, we use HashSet because time complexity to check whether it contains the number is constant or O(1).

private int SumOfDigitSquare(int n)
{
    int sum = 0;
    int i = 0;
    while (n > 0)
    {
        int remainder = n % 10;
        n = n / 10;
        sum += remainder * remainder;
    }

    return sum;
}

public bool IsHappy(int n)
{
    HashSet<int> set = new HashSet<int>();
    while (n != 1 && !set.Contains(n))
    {
        set.Add(n);
        n = SumOfDigitSquare(n);
    }

    return n == 1;
}

• Time Complexity: In the first iteration, we need approximately log n to get the next number. Then, in the second iteration we need log (log n).
  Therefore time complexity would be O(log n) because log n is the dominant part.

    log n + log (log n) + log (log (log n)) + ... = O(log n)
  

• Space Complexity: Imagine if we have 1 million digits and the next number after largest 1 million digit is 81,000,000. Then, the next one will be 65. From this and previous example, we know that how quick the number digits will reduce and once the digits has decreased to 3 digits it will stuck with a number below 243.
  Therefore, if we store all the next number, the total space will be around 243 or constant. Thus, the space complexity is O(1) since in total we will only store around 243 numbers.

Linked List (Floyd’s Cycle Detection Algorithm)#

Similar to previous approach, but this time we use Floyd’s Cycle Detection Algorithm where the underlying implementation uses Two Pointers technique.

private int SumOfDigitSquare(int n)
{
    int sum = 0;
    int i = 0;
    while (n > 0)
    {
        int remainder = n % 10;
        n = n / 10;
        sum += remainder * remainder;
    }

    return sum;
}

public bool IsHappy(int n)
{
    int slowPointer = n;
    int fastPointer = SumOfDigitSquare(n);
    while (fastPointer != 1 && slowPointer != fastPointer)
    {
        slowPointer = SumOfDigitSquare(slowPointer);
        fastPointer = SumOfDigitSquare(SumOfDigitSquare(fastPointer));
    }

    return fastPointer == 1;
}

• Time Complexity: Using previous analysis, the complexity is O(log n) because log n is the dominant part.
• Space Complexity: The complexity is obviously O(1) because we don’t need additional storage to store the next number in order to detect a cycle.

Number Theory#

There is an interesting property in Number Theory that the only cycle in base 10 number is

4 -> 16 -> 37 -> 58 -> 89 -> 145 -> 42 -> 20 -> 4 -> …

Any cycle found must contain above numbers in the chain. Therefore, to detect a cycle we can just hardcode them or even either of them.

private int SumOfDigitSquare(int n)
{
    int sum = 0;
    int i = 0;
    while (n > 0)
    {
        int remainder = n % 10;
        n = n / 10;
        sum += remainder * remainder;
    }

    return sum;
}

public bool IsHappy(int n)
{
    HashSet<int> eightNumberCycle = new HashSet<int>() {4, 16, 37, 58, 89, 145, 42, 20};
    while (n != 1 && !eightNumberCycle.Contains(n))
    {
        n = SumOfDigitSquare(n);
    }

    return n == 1;
}

In below case, we only check whether the next number is 4 or not. If yes, then there must be a cycle. 4 can be replaced by any number from the hardcoded number above.

private int SumOfDigitSquare(int n)
{
    int sum = 0;
    int i = 0;
    while (n > 0)
    {
        int remainder = n % 10;
        n = n / 10;
        sum += remainder * remainder;
    }

    return sum;
}

public bool IsHappy(int n)
{
    while (n != 1 && n != 4) {
        n = SumOfDigitSquare(n);
    }
    return n == 1;
}

• Time Complexity: Using previous analysis, the complexity is O(log n) because log n is the dominant part.
• Space Complexity: The complexity is O(1) because the HashSet that is used to detect a cycle has constant size.