Mathematical explanation and proof. plus two common solutions


  • 0
    C

    I started solving it just according to the definition, and then started wonder why the number must be a either a loop or 1. i think it's a good practice to demonstrate problem solving process. Here is my brief observation to simplify the explanation, hope it would help

    1. Suppose number n has m digit.

    2. Each digit can be maximally 9, so the next number max n' = 81m < n (for any m>=4)
      (e.g. 9999, has 4 digits, next number would be 81*4=324)
      -->so conclude that any number we start, it'll drop under 1000,

    3. For number 1-1000, we can prove by brutal force that it'll either end with 1 or a loop.
      -->for any positive integer, it will either be 1 or loop.

    Below is the program to prove this

    public void proveTheory() throws Exception {
            for (int i = 1; i < 1000; i++) {
                //since it's to prove the theory, we cannot assume a number would either end in 1 or cycle
                //put a limit on the for loop
    
                HashSet<Integer> set = new HashSet<>();
                int num = i;
                for (int j = 0; j < 10000; j++) {
                    if (set.contains(num) || num == 1) break;
                    set.add(num);
                    num = next(num);
                }
    
                if (!set.contains(num) && num != 1) throw new Exception(num + " is neither happy nor loop");
            }
        }
    
        private int next(int num) {
            int next = 0;
            while (num != 0) {
                next += (num % 10) * (num % 10);
                num /= 10;
            }
            return next;
        }
    

    What's provided above is only simple ways to prove it. Wiki has the full definition with more math to narrow down the range of search https://en.wikipedia.org/wiki/Happy_number

    With the above analysis, the question basically becomes cycle detection in linked list, below is two solutions

    Floyd Loop Detection as used in linked list

    public boolean isHappy(int n) {
        int n1 = n, n2 = n;
    
        while (n1 != 1) {
            n1 = next(n1);
            n2 = next(next(n2));
            if (n1 == n2) break;
        }
    
        return n1 == 1;
    
    }
    

    Use HashSet to record visited number

    public boolean isHappy(int n) {
    
        HashSet<Integer> visited = new HashSet<>();
        int num = n;
        while (num != 1 && !visited.contains(num)) {
            visited.add(num);
            num = next(num);
        }
        return num == 1;
    }

Log in to reply
 

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