Happy Number

Problem Statement

What is a happy number?

A number is a happy number if we can reduce a given number to 1 following this process:

-> Find the sum of the square of the digits of the given number. Replace this sum with the old number. We will repeat this process until we can reduce the number to one or it forms a cycle.

That means a cycle is formed like if we started with a number, followed the process to convert it to one, but we reached the number we had stared with then we say it is forming a cycle.

example of a number forming cycle is as follows:

89
8*8+9*9=145
1*1*+4*4+5*5=42
4*4+2*2=20
2*2+0*0=4
4*4=16
1*1+6*6=37
3*3+7*7=58
5*5+8*8=89

So this forms a cycle. Hence not a happy number because this can not be reduced to 1 because it will keep forming 89 every time. If the number is reduced to 1 return true else return false.

Example

19

true

Explanation

1^2+9^2=82

8^2+2^2=68

6^2+8^2=100

1^2+0^2+0^2=1

We can reduce this number to one so it is a happy number.

Approach

This problem is very simple and uses only the basic concept of the set.

What is a set?

Set is an associative container in which unique elements are present.

To solve this problem we will use a set. In the set, we will insert the newly formed number after adding the square of the digits of the number. Now if the element is already present in the set it means that it is forming a loop and we can’t convert the given number into one so this is not a happy number. If the number is reduced to one then the given number is a happy number.

Code

C++ code for Happy Number

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

 bool isHappy(int n) {
        unordered_set<int> tmp;
        while(n != 1)
        {
            if(tmp.find(n) == tmp.end())
                tmp.insert(n);
            else
                return false;
            int sum = 0;
            while(n != 0)
            {
                sum += pow(n % 10,2);
                n = n / 10;
            }
            n = sum;
        }
        return true;
    }

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

true

Java code for Happy Number

import java.util.*;

class Main
{
  static 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;
  }

  public static void main (String[] args) throws java.lang.Exception
  {
    int n = 19;
    boolean result = isHappy(n);
    System.out.print(result);
  }
}

19

true

Complexity Analysis

Time Complexity

O(log N), log N has base 10. So, the time complexity is dependent on the number of digits in the number. And it keeps on decreasing with the logarithmic factor. Thus the time complexity is O(log N).

Space Complexity

O(logN), space is required to store these intermediate numbers. Similar to the time complexity the space complexity is also logarithmmic.