Happy Number Leetcode Solution

Difficulty Level Easy
Frequently asked in Adobe Amazon Apple
algorithms coding Hashing Interview interviewprep LeetCode LeetCodeSolutionsViews 7809

Problem Statement

The problem is to check whether a number is happy number or not.

A number is said to be happy number if replacing the number by the sum of the squares of its digits, and repeating the process makes the number equal to 1. if it does not become 1 and loops endlessly in a cycle which does not include 1, it is not a happy_number.

Example

19
true

Explanation:

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 Number)

2
false

Explanation:

As it is reached to number 4 again, from here it will loop in the chain forever and can never end at 1. Hence given number is not a happy number.

Approach

We can iterate in a while loop and replace the number with sum of the square of its digits until the number becomes 1, with the condition that each new converted number must not had occurred before otherwise we will go into indefinite loop.
For this we can take a set of integers, initially empty and perform following steps:

  1. If the current number is already present in the set return false ( found a loop ).
  2. Else if it is equal to 1 return true.
  3. Else insert the current number into the set and replace the current number with sum of the square of its digits.
  4. Repeat the same process.

Implementation

C++ Program for Happy Number Leetcode Solution

#include <bits/stdc++.h>
using namespace std;

bool isHappy(int n) {
                 
    set<int> s;

    while(s.count(n)==0)
    {
        if(n==1) return true;
        s.insert(n);
        int temp=0;

        while(n)
        {
            temp+= (n%10)*(n%10);
            n/=10;
        }
        n=temp;
    }
    return false;
}

int main()
{ 
    int n=19;
    
    if(isHappy(n)) 
        cout<<"true"<<endl;
    else 
        cout<<"false"<<endl;
    
 return 0;
}

true

Java Program for Happy Number Leetcode Solution

import java.util.*;
import java.lang.*;

class Happy
{  
     public static boolean isHappy(int n) 
     {
        
        Set<Integer> set = new HashSet<Integer>();
        int sum,digit;

        while (set.add(n)) 
        {
            sum = 0;
            while (n > 0) {
                digit = n%10;
                sum += digit*digit;
                n /= 10;
            }
            if (sum == 1)
                return true;
            else
                n = sum;

        }
        return false;
    }
    
    
    public static void main(String args[])
    {
       int n=19;
       System.out.println(isHappy(n));
    }
}
true

Complexity Analysis for Happy Number Leetcode Solution

Time Complexity

O(logn):  Where n is the given number. Cost of finding sum of the square of each digit of a number in chain is log(n) and the number keeps decreasing with the logarithmic factor. Hence complexity = O(logn) + O(loglogn) + O(logloglogn) + ….
Here O(log⁡n) is the dominating part. Hence overall complexity is O(logn).

Space Complexity 

O(logn):  Maximum size of set will also be logarithmic with given number like time complexity.

Translate »