Happy Number

Easy

Write an algorithm to determine if a number n is happy.

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.
  • 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.

Return true if n is a happy number, and false if not.

Example 1:

Input: n = 19
Output: true
Explanation:
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1

Example 2:

Input: n = 2
Output: false

Constraints:

  • 1 <= n <= 231 - 1

Algorithm

  1. isHappy() determines whether a given number is happy or not.
    1. If the number is greater than 0, then calculate remainder by dividing the number with 10.
    2. Calculate square of remainder and add it to a variable result.
    3. Divide number by 10.
    4. Repeat these steps from 1,2 and 3 till the sum of the square of all digits present in number has been calculated.
    5. Finally, return the result.
  2. Define and initialize variable cur_number.
  3. Calculate getSumOfSquareOfDigits
  4. If the result is 1 then the number is a happy number.
  5. Store the ouput of getSumOfSquareOfDigits in a HashSet to check if we are in a loop, if so, the return false.
class Solution {
    public boolean isHappy(int n) {
        Set<Integer> seen = new HashSet<>();
        int cur_number = n;
        while(true){
            cur_number = getSumOfSquareOfDigits(cur_number);
            if(cur_number == 1){
                return true;
            }
            if(seen.contains(cur_number)){
                return false;
            }
            seen.add(cur_number);
        }
    }
    
    private int getSumOfSquareOfDigits(int n){
        int result = 0;
        while(n > 0){
            int remainder = n %10;
            result = result + (remainder * remainder);
            n = n /10;
        }
        return result;
    }
}

Approach 2: Floyd’s Cycle-Finding Algorithm

Intuition

The chain we get by repeatedly calling getSumOfSquareOfDigits(n) is an implicit LinkedListImplicit means we don’t have actual LinkedNode’s and pointers, but the data does still form a LinkedList structure. The starting number is the head “node” of the list, and all the other numbers in the chain are nodes. The next pointer is obtained with our getSumOfSquareOfDigits(n) function above.

Recognizing that we actually have a LinkedList, it turns out that this question is almost the same as detecting if a linked list has a cycle. Therefore we can use Floyd’s Cycle-Finding Algorithm here. This algorithm is based on 2 runners running around a circular race track, a fast runner and a slow runner. In reference to a famous fable, many people call the slow runner the “tortoise” and the fast runner the “hare”.

Regardless of where the tortoise and hare start in the cycle, they are guaranteed to eventually meet. This is because the hare moves one node closer to the tortoise (in their direction of movement) each step.

Cycle Detection
class Solution {

     public int getSumOfSquareOfDigits(int n) {
        int totalSum = 0;
        while (n > 0) {
            int d = n % 10;
            n = n / 10;
            totalSum += d * d;
        }
        return totalSum;
    }

    public boolean isHappy(int n) {
        int slowRunner = n;
        int fastRunner = getSumOfSquareOfDigits(n);
        while (fastRunner != 1 && slowRunner != fastRunner) {
            slowRunner = getSumOfSquareOfDigits(slowRunner);
            fastRunner = getSumOfSquareOfDigits(getSumOfSquareOfDigits(fastRunner));
        }
        return fastRunner == 1;
    }
}
  • Time Complexity : O(logn)
  • Space Complexity : O(1)

Categories: Linked List

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s