C++ 0 ms solution beats 98.32% cpp submissions


  • 0
    P
    int count(int n) {
        int sum = 0;
        while (n) {
            sum += pow(n%10, 2);
            n /= 10;
        }
        return sum;
    }
    bool isHappy(int n) {
        int t = 6;
        while (t--) {
            n = count(n);
            if (n == 1)
                return true;
        }
        return false;
    }

  • 0
    H

    Why you set the count " t " to be 6? Is there any mathematical explanation? thks


  • 0
    T

    I'm curious too, empirical observation? One possiblity: The cycle length is 8 (4, 16, 37, 58, 89, 145, 42, 20). If something takes longer than this, it must be looping. Even the largest possible summed signed int 1999999999 takes 2 steps to enter the cycle and in 1 steps it's already below 1000. Notice that it's t-- which means count will execute 7 times at most. I guess it assumes that the 7th transition will enter the loop at worst, otherwise it will stop on n == 1. Note that the counting series decreases very fast.


  • 0
    X
    This post is deleted!

Log in to reply
 

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