My Java solution: find 1 or 7 when happy sum is a single digit


  • 16
    W

    In order to find a rule to break out the loop, I start calculating 2 and find a loop at 4, then 3,5,6,9 will all go into that loop. So in 1-9, only 1 and 7 are happy numbers. Also I find all numbers' calculation will goes into a single digit at some time. So what I did is just calculate happy sum and when it is a single digit, check if it is 1 or 7 ^.^

    public boolean isHappy(int n) {
            if(n<=0) return false;
            while(true){
                int sum=0;
                while(n!=0){
                  sum+=(n%10)*(n%10);
                  n=n/10;
                }
                if(sum/10==0){
                   if(sum==1||sum==7) return true;
                   else return false;
                }
                n=sum;
            }
        }

  • 8
    I

    Could you prove that mathematically: "Also I find all numbers' calculation will goes into a single digit at some time" ?


  • 0
    1
    This post is deleted!

  • 3
    1

    Proof to "all numbers' calculation will goes into a single digit at some time". I post this as an answer to have a better format than comment.

    The happy sum of a N digit number, Happy(num), will not be larger than Happy(10^(N+1) - 1) = 81N.

    Therefore when N > 3, we always have 81N < 100N < (10^2) * N < 10^N, that is Happy(num) < num / 10, which will eventually reduce the happy sum of any number to smaller or equal to 999, because Happy(9999) < 999.

    Happy(999) = 243, therefore any number larger than 99 and smaller or equal to 999 should have a happy sum smaller or equal to 243, which in turn smaller than 299, which should have the largest happy sum among all numbers in [200, 300).

    Happy(299) = 166, therefore Happy(num) will get to a number smaller or equal to 166 at some step, which in turn smaller than 199.

    1. Happy(199) = 163 < 199.
    1. Happy(99) = 162.

    Combining 1 and 2 above, we know any numbers larger than 100 will be reduced to smaller than 163 at some step, and any numbers smaller than 100 have a happy sum that is smaller or equal to 162, therefore all numbers will be reduced to smaller or equal to 162 at some step.

    Now we only have 162 numbers to deal with, you can simply write a program to verify that their happy sum all get to a single digit at some step.


  • 0
    H

    It will be also accepted If you modify your last if to if(sum == 1) return true;
    Does it mean no sum can reach 7? I'm confusing.


  • 0
    J

    "Therefore when N > 3, we always have 81N < 100N < (10^2) * N < 10^N, that is Happy(num) < num / 10, " don't quite understand.
    think the formula is : Happy(num)<10^N<10^N-1(since we have more than two strictly less than relation whiles.)
    so Happy(999999)<99999, Happy(99999)<Happy(9999)
    Happy(9999)<999, so on and so forth.
    so the largest sum converge to less than 999.


  • 0
    1

    Yes your formula is right, mine is a bit erroneous.


  • 0
    C

    it is best if we can prove number that is less than 163 can be converged to less than 10


  • 0
    S

    some numbers like 1112 will lead to 7. it seems that test cases just don't include that one.


  • 0

    @19thhell Thank you for your proof. Despite some minor mistakes, your proof is still very good.

    For future readers, a quick summary would be:
    suppose num has N digits with N ≥ 3, we can prove something like:
    e.g num = 1666 and N = 4 :
    happy(1666) < happy(9999) < 999
    and happy(999) < 99
    In this analysis, we can prove that all numbers with at least 3 digits would finally end up as a two-digit somewhere in the cycle.

    For the rest (to prove that it ends up as a 1-digit number), here is a proof cited at another post. Unfortunately, it seems like the final resort is still enumeration for numbers with no more than 2 digits.

    Here is my implementation just for reference. It is good to come up with a deceptively simple algorithm that I ended up not understanding and to come to leetcode discussion just to find what I needed.

    
    public class Solution {
        public boolean isHappy(int n) {
            int res = n;
            while (res >= 10) {
                n = res;
                res = 0;
                while (n > 0) {
                    int digit = n % 10;
                    res += digit * digit;
                    n = n / 10;
                }
            }
            return res == 1 || res == 7;
        }
    }
    

    The running time (2017-07-01 17:01:37) wavers between 1ms and 2ms.


Log in to reply
 

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