loading...

JAVA: CODING PROBLEM : HAPPY NUMBER

inspire99 profile image Ganesh Swamypillai ・3 min read

Thank you for 📖 , I 🙏 invite you to my blog at this 🔗: https://gansai.blogspot.com/2020/04/java-coding-happy-number.html

Problem:

Given a number, replace the number by the sum of the squares of its digits, and 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 numbers.

Input: 19

Output: true

Explanation:

1^2 + 9^2 = 82
8^2 + 2^2 = 68
6^2 + 8^2 = 100
1^2 + 0^2 + 0^2 = 1

Solution:

There are many approaches to solve this problem.

  1. Try to solve this, without scrolling down, on your own.
  2. Give yourself some time to think of solution. Keep a timer.
  3. Come back after some time, if you have a solution / pseudocode, you can comment it right away. Otherwise, no problem, you will eventually be able to solve such problems.

If you are interested in the approaches, you can scroll below.

The common bruteforce approach is to :

  1. Set the input as input_number
  2. Take each digit in the input_number. Initialize sum to zero
  3. Square each digit and add to sum.
  4. Now check if sum is 1. If not set the sum as input_number and go to step 1.

package com.technoparadigms.happynumber;


class HappyNumberBruteForce {


    public static void main(String[] args) {
        System.out.println(isHappy(2));
    }


    public static boolean isHappy(int n) {

        int sum = 0;
        while(true){

            sum = getSum(n);
            if(sum == 1){
                return true;
            }            
            else{             
                n = sum;
            }

        }

    }

    private static Integer getSum(Integer input){
        int sum = 0;

        while(input > 0){
            sum+= Math.pow(input%10, 2);
            input /= 10;
        }

        System.out.println("The sum is"+ sum);

        return sum;
    }
}

Can you observe something which can happen in the worst case above?

Yes, we might have endless loop, if 1 is not reached.

happy numbers

So, how can we do better ?

Here are 2 approaches listed in below image.

APPROACHES

SOLUTION

APPROACH 1: Using Set


package com.technoparadigms.happynumber;

import java.util.*;

public class HappyNumberHashSet {

    public static void main(String[] args) {
        System.out.println(isHappy(1111111));
    }



public static boolean isHappy(int n) {
    HashSet<Integer> set = new HashSet<Integer>();

    while(!set.contains(n)){
        set.add(n);

        n = getSum(n);

        if(n==1)
            return true;
    }

    return false;
}

public static int getSum(int n){
    int sum =0;
    while(n>0){
        sum+=(n%10)*(n%10);
        n=n/10;
    } 
    return sum;    
}

}

APPROACH 2: Using Two Pointers

TWO POINTERS



package com.technoparadigms.happynumber;

public class HappyNumberTwoPointers {


    public static void main(String[] args) {
        System.out.println(isHappy(19));
    }



public static boolean isHappy(int n) {


    int slow = n, fast = n;
    while(true){
        slow = getSum(slow);
        fast = getSum(fast);
        fast = getSum(fast);

        if(slow == fast){

            break;
        }

    }


    return slow == 1;
}

public static int getSum(int n){
    int sum =0;
    while(n>0){
        sum+=(n%10)*(n%10);
        n=n/10;
    } 


    return sum;    
}


}


To read the mathematical nature of Happy Number, read the wiki - https://en.wikipedia.org/wiki/Happy_number

🖐, 🙏 for 📖, you can
Buy Me A Coffee

Posted on by:

Discussion

markdown guide