Happy Number

Problem

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

Definition

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.
  • 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.

Return true if n is a happy number, and false if not.

Example

Example 1:

Input: n = 19
Output: true

Explanation:
19 is a happy number
1^2 + 9^2 = 82
8^2 + 2^2 = 68
6^2 + 8^2 = 100
1^2 + 0^2 + 0^2 = 1
So, the cycle is 19 -> 82 -> 68 -> 100 -> 1

Example 2:

Input: n = 2
Output: false

Solution

The key to solve this problem is the stop condition for the loop.

Method 1 - Using Set to Check Visited

public 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 int getSum(int n) {
	int sum = 0;
	while (n > 0) {
		sum += (n % 10) * (n % 10);
		n = n / 10;
	}
	return sum;
}

Method 2 - Using Floyd Cycle Detection

Lets rename function getSum to getNext like in linked list. More: Floyd Cycle-Finding Algorithm.

public boolean isHappyFloydCycleDetection(int n) {
	int slow = n;
	int fast = getNext(n);

	while(fast != 1 && fast != slow) {
		slow = getNext(slow);
		fast = getNext(getNext(fast));
	}

	return fast == 1;
}

public int getNext(int n){ 
	return getSum(n);
}