Day 10/100 Happy Number

 Day 10/100 Happy Number

Happy Numbers are all alike

A happy number is a number that is having the sum of the squares of the digit to equals to 1. If it isn't 1, repeat until it does. Those numbers that does not reach 1, are unhappy numbers.

This is LeetCode 202, for those following LeetCode challenges. There are so many solutions. However, like most coding problems, there are different considerations regarding optimizations. Do you optimize for speed, or for memory?

This is a question that many programmers don't think about. Most of them simply put everything into hash, and be done with it. A little careful consideration will yield an analysis that basically tells you that the sequence of happy numbers will not exceed that of 999. In fact, on the leetcode official solution, that number was pegged at 243, due to the fact that the next number in sequence after 999 is 243.

That's nice. However, that is not good enough for me. Remember the high/low, mountain/valley problem? We only mark the top of the hill, or the bottom of the valley. In those cases, what are the numbers? Here is my first version of happy number program:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXENTRY 1000
int Mark[MAXENTRY];
int happyLast;
int happyMax;
int happyMin;

int nextN(int M) {
  int N=0;
  while (M>0) {
    N+=(M%10)*(M%10);
    M/=10;
  }
  return N;
}

 

int IsHappy(int N) {
  if (N<1) return 0;
  while (1) {
    if (N<MAXENTRY) {
      if (N==1) return 1;
      if (Mark[N]) return 0;
      Mark[N]=1;
    }
    happyLast=N; N=nextN(N);
    if (happyLast>N && happyMin>N) happyMin=N;
    if (happyLast<N && happyMax<N) happyMax=N;
  }
}

 

int main (int argc, char *argv[] ) {
  int n,i;
  for (n=50000;n;n--) {
    for (i=0;i<MAXENTRY;i++) Mark[i]=0;
    happyMin=MAXENTRY; happyMax=0;
    if (IsHappy(n)) 
      printf("%d is happy. %d %d\n",n,happyMin,happyMax);
    else 
      printf("%d is unhappy. %d %d\n",n,happyMin,happyMax);
  }
  return 0;
}

If you notice, I track the minimum and maximum for each happy numbers. This is because I want to see for myself, what the range is for each numbers. You don't see that anywhere else. It's as if people just blindly copy solutions from each others. Speaking of which, here's the other solution, version 2. Diff is between version 1 and version 2:

19a20
> //  printf("%d\n",N);
28c29,36
<       if (Mark[N]) return 0;
---
>       if (N==100) return 1;
>       if (N==130) return 1;
>       if (N==2) return 0;
>       if (N==3) return 0;
>       if (N==4) return 0;
>       if (N==145) return 0;
>       if (N==162) return 0;
> //      if (Mark[N]) return 0;

As you can see, I no longer use the array to mark visited numbers. This is a great savings for memory. You also see different numbers for happy, such as 100 and 130, as well as for unhappy numbers.

By the way, the official solution shows that you only need to check number 4 for unhappy number. Somebody also pointed out that if the number is below 10, then only number 1 and 7 are happy. So that certainly saves some comparison. 

But is it faster? Let's see the timings.

Version 1: This version is the simple version, uses an array.

user 0m1.044s

Version 2: Skips the array. Uses the numbers as above.

user 0m0.390s

Version 3: Only checks number 1 and 4.

user 0m0.471s

Version 4: Removes checks for 3 and 162.

user 0m0.353s

As you can see, the simple version 1 takes the longest, and uses the most memory. Version 2, which takes account of actual minimum and maximum for each number, is not only memory efficient, but also much faster.

Version 3, which does only minimal checks, takes no memory and relatively fast, but is still slower than version 2.

Version 4, takes a look at the numbers, and removes the least important ones. There's only a solitary 3, and a smatterings 162. The program runs slightly faster without them.

Here is the last and most efficient version 4:

#include <stdio.h>

int nextN(int M) {
  int N=0;
  while (M>0) {
    N+=(M%10)*(M%10);
    M/=10;
  }
  return N;
}

int IsHappy(int N) {
  if (N<1) return 0;
  while (1) {
    if (N==1 || N==100 || N==130) return 1;
    if (N==2 || N==4   || N==145) return 0;
    N=nextN(N);
  }
}

int main (int argc, char *argv[] ) {
  int n,i;
  for (n=50000;n;n--) {
    if (IsHappy(n)) printf("%d is happy\n",n);
    else printf("%d is unhappy\n",n);
  }
  return 0;
}

One more thing:

That is not the only speed improvement possible. I can also do frequency analysis, looking at the most visited numbers, and check that. But that is an endeavor without end.  In case you're wondering, though: 4, 16, 20, 37, 42, 58, 89, 145 are frequently visited numbers, and those are the numbers in the cycle. 

Running time: user 0m0.290s