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 –
- Find the sum of the digits of the number.
- If sum is one, return true, we found our happy number.
- Keep adding to some list/set if it’s already not there.
- If sum is already in a list/set, return false.
- 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