Massive Algorithms: LeetCode --- 202. Happy Number

LeetCode --- 202. Happy Number

LeetCode --- 202. Happy Number | mkyforever
Write an algorithm to determine if a number is "happy".
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, and 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 numbers.
Example: 19 is a happy number

1^2 + 9^2 = 82  8^2 + 2^2 = 68  6^2 + 8^2 = 100  1^2 + 0^2 + 0^2 = 1

这道题的要求是判断一个数是不是"happy"的。关于"happy"数字的定义：从这个数字（正整数）开始，用其各个数位上数字的平方和替换这个数字，直到等于1或者出现重复。如果最后等于1说明是"happy"数组。
简单模拟，用Hash记录出现过的数组，用以判断是否出现环。
时间复杂度：O(n)
空间复杂度：O(n)

use hash map to keep all the previous calculated number, if it is loop, exist with false, otherwise it will become 1.

public boolean isHappy(int n) {
Set<Integer> set = new HashSet<>();
while(set.add(n)) {
n = sumSquares(n);
if(n == 1) return true;
}
return false;
}
private int sumSquares(int n) {
int sum = 0;
while(n != 0) {
int digit = n % 10;
sum += digit * digit;
n /= 10;
}
return sum;
}

https://leetcode.com/discuss/77996/simple-and-short-solution-in-java
public boolean isHappy(int n) { if (n <= 0) return false; HashSet<Integer> set = new HashSet<Integer>(); while(n !=1 && !set.contains(n)) { set.add(n); int m = n; n = 0; while(m != 0) { n += (m%10)*(m%10); m = m/10; } } if (n == 1) return true; else return false; }
http://rosettacode.org/wiki/Happy_numbers#Java

   public static boolean happy(long number){
       long m = 0;
       int digit = 0;
       HashSet<Long> cycle = new HashSet<Long>();
       while(number != 1 && cycle.add(number)){
           m = 0;
           while(number > 0){
               digit = (int)(number % 10);
               m += digit*digit;
               number /= 10;
           }
           number = m;
       }
       return number == 1;
   }

https://sisijava.wordpress.com/

   public boolean isHappy(int n) {

        HashSet<Integer> happy = new HashSet<Integer>();

        int sum = 0;

        while(!happy.contains(n)){

            sum =0;

            happy.add(n);

            int tmp = 0;

            while(n > 0){

                tmp = n % 10;

                n = n / 10;

                sum = sum + tmp*tmp;

}

            if(sum == 1){

                return true;

}

            n = sum;

}

        return false;

}

https://github.com/checkcheckzz/coding-questions/blob/master/problem/Happy%20Number.cpp

http://blog.csdn.net/yuanhisn/article/details/46118297

A happy number is defined by the following process. Starting with any positive integer, replace the number by the sum of the squares of its digits, and 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 numbers, while those that do not end in 1 are unhappy numbers. Display an example of your output here.

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.

http://www.jiuzhang.com/solutions/happy-number/

    private int getNextHappy(int n) {
        int sum = 0;
        while (n != 0) {
            sum += (n % 10) * (n % 10);
            n /= 10;
        }
        return sum;
    }
    
    public boolean isHappy(int n) {
        HashSet<Integer> hash = new HashSet<Integer>();
        while (n != 1) {
            if (hash.contains(n)) {
                return false;
            }
            hash.add(n);
            n = getNextHappy(n);
        }
        return true;
    }

https://leetcode.com/discuss/59684/beat-easy-understand-java-solution-with-brief-explanation
public boolean isHappy(int n) { Set<Integer> inLoop = new HashSet<Integer>(); int squareSum,remain; while (inLoop.add(n)) { squareSum = 0; while (n > 0) { remain = n%10; squareSum += remain*remain; n /= 10; } if (squareSum == 1) return true; else n = squareSum; } return false; }

X. O(1) Space

good idea. one thing I wanna point out is that the space complexity of hashset impl is low(it's bounded).

https://leetcode.com/discuss/33349/o-1-space-java-solution
public boolean isHappy(int n) { int x = n; int y = n; while(x>1){ x = cal(x) ; if(x==1) return true ; y = cal(cal(y)); if(y==1) return true ; if(x==y) return false; } return true ; } public int cal(int n){ int x = n; int s = 0; while(x>0){ s = s+(x%10)*(x%10); x = x/10; } return s ; }
https://leetcode.com/discuss/32842/use-the-same-way-as-checking-cycles-in-a-linked-list
bool isHappy(int n) { int A = nxt(n), B = nxt(nxt(n)); while (A != 1 && A != B) { A = nxt(A); B = nxt(B); B = nxt(B); } return A == 1; } private: int nxt(int num) { int res = 0; while (num) { res += (num % 10) * (num % 10); num /= 10; } return res; }
X. Proof
https://leetcode.com/discuss/71625/explanation-those-posted-algorithms-mathematically-valid

First of all, it is easy to argue that starting from a number I, if some value - say a - appears again during the process after k steps, the initial number I cannot be a happy number. Because a will continuously become a after every k steps.

Therefore, as long as we can show that there is a loop after running the process continuously, the number is not a happy number.

There is another detail not clarified yet: For any non-happy number, will it definitely end up with a loop during the process? This is important, because it is possible for a non-happy number to follow the process endlessly while having no loop.

To show that a non-happy number will definitely generate a loop, we only need to show that for any non-happy number, all outcomes during the process are bounded by some large but finite integer N. If all outcomes can only be in a finite set (2,N], and since there are infinitely many outcomes for a non-happy number, there has to be at least one duplicate, meaning a loop!

Suppose after a couple of processes, we end up with a large outcome O1 with D digits whereD is kind of large, say D>=4, i.e., O1 > 999 (If we cannot even reach such a large outcome, it means all outcomes are bounded by 999 ==> loop exists). We can easily see that after processing O1, the new outcome O2 can be at most 9^2*D < 100D, meaning that O2 can have at most 2+d(D) digits, where d(D) is the number of digits D have. It is obvious that2+d(D) < D. We can further argue that O1 is the maximum (or boundary) of all outcomes afterwards. This can be shown by contradictory: Suppose after some steps, we reach another large number O3 > O1. This means we process on some number W <= 999 that yields O3. However, this cannot happen because the outcome of W can be at most 9^2*3 < 300 < O1.

Done.

https://leetcode.com/discuss/97703/all-you-need-to-know-about-testing-happy-number

for those who are less patient, here is some findings,

(1) for a positive integer n, n is either a happy number or unhappy with cycle length 7.

(2) digitSquareSum(n) < n for all n>99

(3) there are 19 happy numbers and 80 unhappy numbers in [1,99]

(4) happyNumLess100 = [1, 7, 10, 13, 19, 23, 28, 31, 32, 44, 49, 68, 70, 79, 82, 86, 91, 94, 97]

(5) for these numbers the corresponding update count to become 1 is stepcnt = [0, 5, 1, 2, 4, 3, 3, 2, 3, 4, 4, 2, 5, 3, 3, 2, 4, 4, 3]

let g(n) denote digitSquareSum function, eg. g(4) = g(16), g(19) = 82 etc

for nin [1,10), g(n)>=n, since g(n)=n*n>=nwith equality hold only for n=1
for other n with only highest digit nonzero (eg. 10, 90, 500, 4000, 20000, etc), g(n)<n
and we can factor n into sum of numbers with only highest digit nonzero, eg. 12045 = 10000 + 2000 + 40 + 5

in this way, we can show for any n>=100, g(n) < n

by calculate all cases in [1,200],

L1 = [digitSquareSum(n) - n for n in range(1,200)]
L2 = list(filter(lambda x: x>0, L1))
L3 = list(filter(lambda x: x>0, L1[99:]))
len(L1), len(L2), len(L3)
>>> (199, 50, 0)
max(L2), L1.count(max(L2)), 1 + L1.index(max(L2))
>>> (72, 1, 9)
min(L2), L1.count(min(L2)), 1 + L1.index(min(L2))
>>> (2, 1, 2)

the test shows that

(1) for all n>=100, g(n) < n.

(2) there are only 50 number such that g(n) < n, among them for g(n)-n

(3) the unique largest is 9 (g(9)-9 = 72), the unique smallest is 2 (g(2) - 2 = 2).

which shows a surprising result, there is only two cases for any positive integer n

(1) n is a happy number

(2) n is not happy and have cycle length 7 (we will further verify about the cycle length soon)

this can be verified like below. the algorithm is basically

Algorithm 1
input: n (positive integer)
func g = digitSquareSum
while n!=1 and n's current value not appeared in this calculation process
    n= g(n)
output: True if n==1, false otherwise

but we have showed,

(1) for all n>=100, the update step (n= g(n)) reduce the value of n

(2) a loop exist if and only if update have both decreasing and increasing effect in the whole process (the only case of equality is 1, which is excluded at first)

(3) increasing update can only happen for 50 numbers, all of them less than 100

so if we have a True table for all numbers less than 100 indicating happiness, denote it as HappyTable, then algorithm could be changed to

Algorithm 2
input: n (positive integer)
func g = digitSquareSum
while n>99
    n = g(n)
output: HappyTable(n)

if we use function isHappy previously showed (return 0 if n is happy otherwise return the smallet cycle length)

mylist = [isHappy(n) for n in range(1,100)]
happyList = [i+1 for i, val in enumerate(mylist) if val==0]
unhappyList = [i+1 for i, val in enumerate(mylist) if val!=0] # or equivalently if val==7
len(mylist), len(happyList), len(unhappyList)
>>> (99, 19, 80)
happyList
>>> [1, 7, 10, 13, 19, 23, 28, 31, 32, 44, 49, 68, 70, 79, 82, 86, 91, 94, 97]

http://www.chenguanghe.com/happy-number/
http://www.geeksforgeeks.org/happy-number/
A number will not be a Happy Number when it makes a loop in its sequence that is it touches a number in sequence which already been touched. So to check whether a number is happy or not, we can keep a set, if same number occurs again we flag result as not happy.

We can solve this problem without using extra space and that technique can be used in some other similar problem also. If we treat every number as a node and replacement by square sum digit as a link, then this problem is same as finding a loop in a linklist :

So as proposed solution from above link, we will keep two number slow and fast both initialize from given number, slow is replaced one step at a time and fast is replaced two steps at a time. If they meet at 1, then the given number is Happy Number otherwise not.

int numSquareSum(int n)

{

    int squareSum = 0;

    while (n)

{

        squareSum += (n % 10) * (n % 10);

        n /= 10;

}

    return squareSum;

}

//  method return true if n is Happy number

bool isHappynumber(int n)

{

    int slow, fast;

    //  initialize slow and fast by n

    slow = fast = n;

do

{

        //  move slow number by one iteration

        slow = numSquareSum(slow);

        //  move fast number by two iteration

        fast = numSquareSum(numSquareSum(fast));

}

    while (slow != fast);

    //  if both number meet at 1, then return true

    return (slow == 1);

}

https://github.com/kaushal02/CP/blob/master/Self-topics/Happy%20numbers.cc
Read full article from LeetCode --- 202. Happy Number | mkyforever

LeetCode --- 202. Happy Number

let g(n) denote digitSquareSum function, eg. g(4) = g(16), g(19) = 82 etc

the test shows that

which shows a surprising result, there is only two cases for any positive integer n

but we have showed,

Labels

Popular Posts