DEV Community

Akhil
Akhil

Posted on

Happy number revisiting hare and tortoise. Connecting the dots !

Question: Give a number n, determine if it's a happy number.
A number is called happy if it leads to 1 after a sequence of steps wherein each step number is replaced by the sum of squares of its digit that is if we start with Happy Number and keep replacing it with digits square sum, we reach 1.

So for n = 19, the sequence of steps are :
1^2 + 9^2 = 82
8^2 + 2^2 = 68
6^2 + 8^2 = 100
1^2 + 0^2 + 0^2 = 1
As we reached to 1, 19 is a Happy Number.

Brute Force:

Brute force approach would be :
1> find sum of squares of digit of each number,
2>add them to a set
3> repeat 1 & 2 and if we come across a number which is present in a set then the number is not a happy number
4> if we reach 1, number is a happy number.

So based on this let's write our code:

var happy = function(n){
    let set = new Set();
    while(n != 1){
         let temp = n;
         let sum = 0;
         while(temp!=0){
              sum += (temp%10) * (temp%10);
              temp = temp/10;
         }
         if(set.has(sum)) return false;
         set.add(sum);
         n = sum;
    }
    return n == 1;
}
Enter fullscreen mode Exit fullscreen mode

If you're with me till here ? Awesome ! Now let's think about optimizing it. Here we're using O(n) space to store the number. So let's try to convert it to O(1).

Let's revisit our question, the question states that if the number doesn't reach 1, that is it loops around then it's not a happy number.

As you might remember from my loopy linked list here: https://dev.to/akhilpokle/loopy-linkedlist-two-pointers-pattern-2fbl

Alt Text

So, since in this problem we get stuck in a loop, using hare and tortoise in this context to detect loop might be useful.

Let's try to convert the loopy linked list code to work for this problem.

// modifying slow and fast pointers
slow = computeSquare(n);
fast = computeSquare(sumSquare(n));
Enter fullscreen mode Exit fullscreen mode

That's it!


var happy = function(num){
    let slow = computeSquare(num);
    let fast = computeSquare(computeSquare(num));
    while(slow != fast){
         slow = computeSquare(slow);
         fast = computeSquare(computeSquare(fast));
    }
    return slow == 1;
}

var computeSquare = function(num){
    let temp = num;
    let sum = 0;
    while(temp != 0){
         sum += (temp%10) * (temp%10);
         temp = temp/10;
    }
    return sum;
}

Enter fullscreen mode Exit fullscreen mode

Smart eh ? This is how you should connect the dots! When I wrote about loopy linkedlist, you might be thinking that you won't use hare and tortoise elsewhere, but here we are using the same concept again!

github:https://github.com/AKHILP96/Data-Structures-and-Algorithms/blob/master/problems/happyNumber.js

Buy Me A Coffee

Oldest comments (0)