Short 4ms C++ solution


  • 10
    D

    If the next number in the sequence is 1, then the original number was happy. If it was not happy, we enter a cycle that contains the number 4. We could use a cycle detection strategy to do this also, or just test for a given number in the (short) cycle as done here.

    class Solution {
    public:
        bool isHappy(int n) {
            while (true) {
                if (n == 1) { return true; }
                if (n == 4) { return false; }
                int next = 0;
                while (n) { next += (n % 10) * (n % 10), n /= 10; }
                n = next;
            }    
        }
    };

  • 2
    J

    In your code, I can come to that all number will end with 1(happy) or 4(unhappy),
    Can you prove that in math?


  • 1
    L

    From Wiki, in case you have not seen it:
    <wiki>
    If n is not happy, then its sequence does not go to 1. Instead, it ends in the cycle:

    4, 16, 37, 58, 89, 145, 42, 20, 4, ...
    To see this fact, first note that if n has m digits, then the sum of the squares of its digits is at most 9^2 m, or 81m.

    For m=4 and above,

    n\geq10^{m-1}>81m
    so any number over 1000 gets smaller under this process and in particular becomes a number with strictly fewer digits. Once we are under 1000, the number for which the sum of squares of digits is largest is 999, and the result is 3 times 81, that is, 243.

    In the range 100 to 243, the number 199 produces the largest next value, of 163.
    In the range 100 to 163, the number 159 produces the largest next value, of 107.
    In the range 100 to 107, the number 107 produces the largest next value, of 50.
    Considering more precisely the intervals [244,999], [164,243], [108,163] and [100,107], we see that every number above 99 gets strictly smaller under this process. Thus, no matter what number we start with, we eventually drop below 100. An exhaustive search then shows that every number in the interval [1,99] either is happy or goes to the above cycle.

    The above work produces the interesting result that no positive integer other than 1 is the sum of the squares of its own digits, since any such number would be a fixed point of the described process.

    There are infinitely many happy numbers and infinitely many unhappy numbers. Consider the following proof:

    1 is a happy number, and for every n, 10n is happy since its sum is 1
    and for every n, 2 × 10n is unhappy since its sum is 4 and 4 is an unhappy number.
    <wiki>


  • 0
    J

    thanks very much
    :)


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.