Lets Code Them Up!

Happy Number

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

A 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, 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.

Return True if n is a happy number, and False if not.

Example: 

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

Solution

From the problem statement it is clear –

  1. Find the sum of the digits of the number.
  2. If sum is one, return true, we found our happy number.
  3. Keep adding to some list/set if it’s already not there.
  4. If sum is already in a list/set, return false.
  5. If none of the above conditions are met, keep repeating above steps for every new sum.

The time complexity of this solution is O(log n) where n is the input number. Space complexity is O(log n) where n is the input number.

/**
 * HappyNumber.java
 * Purpose: Determine if a number is happy
 *
 * @author Megha Rastogi
 * @version 1.0 07/13/2020
 */
class HappyNumber {

    // Set to track the sum of squares encountered till now
    HashSet<Integer> cache = new HashSet<Integer>();
    
    /**
     * Determine if a number is happy
     *
     * @param integer, n
     * @return boolean, ans
     */
    public boolean isHappy(int n) {
    
        // find sum of squares of digits
        int sum = findSum(n);
        
        // if sum is 1, we found a happy number
        // return true
        if(sum == 1)
            return true;
            
        // if sum is already present in the cache
        // number is not happy, return false
        if(cache.contains(sum))
            return false;
            
        // add sum to cache
        cache.add(sum);
        
        // Find if the new number is happy or not
        return isHappy(sum);
    }
    
    /**
     * Determine sum of squares of each
     * digit in number
     *
     * @param integer, n
     * @return integer, sum
     */
    public int findSum(int n){
        
        // variable to keep track of sum
        int sum = 0;
        
        // Find each digit of the number and
        // add square of that digit to sum
        while(n > 0){
        
            // determine remainder, last digit
            int rem = n % 10;
            
            // add sqaure of remainder to sum
            sum += (rem * rem);
            
            // divide number by 10 to loose the last digit
            n = n/10;
        }
        
        // return sum of squares of each digit
        return sum;
    }
}

Source – leetcode

Code – HappyNumber.java

Megha

,
,