Happy Number

Problem

Write an algorithm to determine if a number n 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.
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.

Return true if n is a happy number, and false if not.

Constraints

1 <= n <= 2³¹ - 1

Solution

The problem Happy Number can be solved by identifying possible cycles. When given process is executed, there are 3 possible outcomes.

Given number converges to 1
Given number gets caught in a cycle
Given number diverges

I’ll first examine if a given number can diverge. Let x be an integer with n digits where all digits are 9, which produces the biggest possible outcome within numbers with n digits. In order for x to diverge, sum of the squares of its digits needs to be larger than x, meaning it needs to have at least n + 1 digits. In other words, an equation 10ⁿ <= 81 * n needs to hold true for x to diverge. Since this equation only holds true when n <= 2, an integer with 3 or more digits cannot produce an outcome with more digits, and therefore, x cannot diverge.

Next, I’ll consider the range in which elements in the cycle can exist. Let x once again be an integer with n digits where all digits are 9. If an outcome of x has less digits than n, then we know that every number with n digits will produce a number smaller than itself. In other words, if 10^{n - 1} > 81 * n holds true, numbers with n digits will converge or oscillate within the range of n-1 digits at most. Since this equation holds true when n > 3, an integer with 4 or more digits will eventually produce an outcome within a range of 3 digits when the given process is repeated. Combining this knowledge with the finding from above, all numbers will eventually produce an outcome of 3 or less digits which will then converge or oscillate in that range since an integer with 3 or less digits can only produces an outcome of 3 digits at most. More specifically, every number will eventually produce an outcome within the range of [1, 243], which will then converge or oscillate within the same range, as 243 is the largest number that can be produced by 3 digit integer.

Based on these findings, I’ll write a code to brute-force every possible cycles that can be produced by an integer from the range [1, 243]. First, for every integer in [1, 243], given process is repeated and recorded until it produces 1 or a duplicate conversion is found, in which case all recorded conversions are saved to a hash map. At this point, we have a list of conversions that lead to a cycle. Next, all recorded conversions are used in creating linked lists where conversion from a to b denotes a connection from node A to node B. After all nodes are set, Floyd’s cycle-finding algorithm is used in finding the exact nodes that forms a cycle. By removing all duplicate, I’m able to find that there is only 1 possible cycle 4 -> 16 -> 37 -> 58 -> 89 -> 145 -> 42 -> 20 -> 4.

In summary, when given process is repeated, every integer will eventually produce an outcome of either 1 or 4. By excluding numbers that produce 4, it is possible to identify happy numbers.

Implementation

#include <iostream>
#include <map>
#include <vector>
using namespace std;

class ListNode
{
  public:
    int val;
    ListNode *next;

    ListNode() : val(0), next(NULL) {}
    ListNode(int _val) : val(_val), next(NULL) {}
    ListNode(int _val, ListNode *_next) : val(_val), next(_next) {}
};

int main(void)
{
    map<int, int> loop;
    for (int i = 1; i <= 243; i++)
    {
        map<int, int> nums;
        nums.insert(loop.begin(), loop.end());

        int num = i;
        while (num != 1)
        {
            int bak = num, sum = 0;
            do
            {
                int digit = num % 10;
                sum += digit * digit;
            } while (num /= 10);
            num = sum;

            if (nums.find(bak) != nums.end())
            {
                loop.insert(nums.begin(), nums.end());
                break;
            }
            nums[bak] = num;
        }
    }

    vector<ListNode *> heads;
    for (int i = 0; i <= 243; i++)
        heads.push_back(new ListNode(i));

    for (auto entry : loop)
        heads[entry.first]->next = heads[entry.second];

    loop.clear();
    for (ListNode *head : heads)
    {
        ListNode *tortoise = head;
        ListNode *hare = head;

        while (hare != NULL && hare->next != NULL)
        {
            tortoise = tortoise->next;
            hare = hare->next->next;

            if (tortoise == hare)
            {
                while (tortoise != hare)
                {
                    tortoise = tortoise->next;
                    hare = hare->next;
                }

                do
                {
                    if (loop.find(hare->val) != loop.end())
                        break;
                    loop[hare->val] = hare->next->val;
                } while (tortoise != (hare = hare->next));
                break;
            }
        }
    }

    string ret;
    while (!loop.empty())
    {
        int from, to;
        map<int, int>::iterator it = loop.begin();

        do
        {
            from = it->first, to = it->second;
            loop.erase(it);
            cout << from << " -> ";
        } while ((it = loop.find(to)) != loop.end());
        cout << to << endl;
    }

    for (int i = 0; i <= 243; i++)
        delete heads[i];
}

class Solution
{
  public:
    bool isHappy(int n)
    {
        while (!(n == 1 || n == 4))
        {
            int sum = 0;
            do
            {
                int digit = n % 10;
                sum += digit * digit;
            } while (n /= 10);
            n = sum;
        }

        return n == 1;
    }
};

Eui Chul Chung

Problem

Constraints

Solution

Implementation