#include <bits/stdc++.h>

using namespace std;

// Problem 202. Happy Number

// 1 <= n <= 2^31 - 1 = 2147483647 (10 digits)

// 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.

class Solution {    
public:
    vector<int> m_digits;
    // set used to detect a cycle.
    set<int> m_sums;

    // sets m_digits with the digits in n
    void getDigits(int n)
    {
        if (n < 10)
        {
            m_digits.push_back(n);
            return;
        }
        int digit = n%10;
        int next = n/10;
        m_digits.push_back(digit);
        return getDigits(next);
    }
    
    bool isHappy(int n) {
        int sum = 0;
        int loopCount = 0;
        
        while (n != 1)
        {
            sum = 0;
            
            m_digits.clear();
            
            getDigits(n);
            
            cout << loopCount << " num: " << n << "; vector: ";

            // sum of the squares of the digits
            for (auto i: m_digits)
            {
                cout << i << " ";
                sum += pow(i,2);
            }
            cout << "; sum: " << sum << endl;
            
            n = sum;
            
            if (m_sums.count(sum))
            {
                cout << "cycle detected: sum: " << sum << endl;
                break;
            }
            
            m_sums.insert(sum);
            
            loopCount++;
        }
        
        if (n == 1)
            return true;
        else
            return false;
    }
};

int main()
{
    Solution s;
    int n;
    cout << "Input number: ";
    cin >> n;

    bool result = s.isHappy(n);
    
    cout << "isHappy: " << result << endl;
    
    return 0;

}