In this tutorial, I am going to discuss a very interesting problem to determine if a number is happy or not.
Given a number n, we have to write a code to check whether a number is happy or not.
Happy Number
Take any positive integer, and replace the number with the sum of the squares of its digits. Repeat the process until the number equals 1 (where it will stay). If it’s equal to 1 then it’s a happy number. If it loops endlessly in a cycle which does not include 1 then it’s not a happy number.
Those numbers for which this process ends in 1 are happy numbers.
For Example –
Example 1:
Input : 19, Output: true
Step 1: 1^2 + 9^2 = 82
Step 2: 8^2 + 2^2 = 68
Step 3: 6^2 + 8^2 = 100
Step 4: 1^2 + 0^2 + 0^2 = 1 (The number ends at 1, So it’s a happy number).
Example 2:
Input : 20, Output : false
Step 1: 2^2 + 0^2 = 4
Step 2: 4^2 = 16
Step 3: 1^2 + 6^2 = 37
Step 4: 3^2 + 7^2 = 58
Step 5: 5^2 + 8^2 = 89
Step 6: 8^2 + 9^2 = 145
Step 7: 1^2 + 4^2 + 5^2 = 42
Step 8: 4^2 + 2^2 = 20 (Loop occurs)
We have discussed the problem statement with the help of multiple examples. How do we check whether a number n is happy or not?
Here is the list of programming questions on –
Happy Number LeetCode Solution – Java Code
In this problem, the tricky part is to detect a loop. We have to make sure that the process of doing the square of digits of a number and repeating the same process does not loop endlessly (In case the number is not a happy number).
To solve this problem, I am using an additional data structure HashSet. Why we are using HashSet? Because the lookup time in HashSet is O(1) as compared to other data structures.
In HashSet, we store the computed sum and at each iteration, we check whether a computed sum is present in HashSet or not.
Here are the following steps to solve this problem –
i) Declare a set to store unique values.
ii) Calculate the sum of the square of digits of a number.
iii) Run a while loop until the sum is not equal to 1. Calculate the current sum of squares based on the previous sum of squares. Check if the current sum of the square of digits of a number is in the HashSet. If it is, then return false.
Find All Duplicates in an Array without using Extra Space
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 |
//Java Code to Check Happy Number public class HappyNumber { public static boolean isHappy(int num) { int calSum = calculateSum(num); Set<Integer> numberSet = new HashSet<>(); numberSet.add(calSum); //Run this loop, if a number is not equal to 1 while(calSum != 1) { int currentSum = calculateSum(calSum); if(numberSet.contains(currentSum)) { return false; } calSum = currentSum; numberSet.add(currentSum); } return true; } private static int calculateSum(int num) { int sum = 0; while(num != 0) { int rem = num%10; sum = sum + (rem * rem); num = num/10; } return num; } public static void main(String[] args) { //int num = 19; int num = 20; System.out.println(isHappy(num)); } } |
Programming Questions on Linked List
Happy Number using Recursion in Java
In this example, let’s solve this problem using recursion. I have already explained the algorithm the logic remains the same. The only difference is we are solving the problem recursively as compared to the iterative approach.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 |
//Using recursion class Solution { public boolean isHappy(int n) { //Declare Hashset Set<Integer> st = new HashSet<>(); return isHappyHelper(n, st); } private boolean isHappyHelper(int n, Set<Integer> st) { if(n == 1) { return true; } int calcSum = calculateSum(n); if(st.contains(calcSum)) { return false; } //Add the calculated sum st.add(calcSum); //Recursively call the method return isHappyHelper(calcSum, st); } //Logic to calculate the sum private int calculateSum(int n) { int sum = 0; while(n != 0) { int rem = n % 10; sum = sum + rem * rem; n = n/10; } return sum; } } |
Most Popular Data Structure Books
