1. Overview
We often solve mathematical problems in programming. Determining whether a number is a happy number is an interesting task.
In this tutorial, we’ll understand how a happy number is defined and explore how to implement a Java program to check whether a given number is a happy number.
2. Understanding the Happy Number
A happy number reaches 1 through repeated replacement by the sum of the squares of its digits. Conversely, a non-happy (sad) number gets caught in an infinite cycle without ever reaching 1.
As usual, a couple of examples can help us quickly understand the happy number definition:
Given number: 19
19 -> 1^2 + 9^2 = 82
82 -> 8^2 + 2^2 = 68
68 -> 6^2 + 8^2 = 100
100 -> 1^2 + 0^2 + 0^2 = 1
1
As the example above shows, we reached 1 in the end for the input number 19. Therefore, 19 is a happy number. Similarly, more happy number examples are 7, 10, 13, 23, etc.
However, if the input is 15, we’ll never reach 1:
Given number: 15
15 -> 1^2 + 5^2 = 26
26 -> 2^2 + 6^2 = 40
40 -> 4^2 + 0^2 = 16
+---> 16 -> 1^2 + 6^2 = 37
| 37 -> 3^2 + 7^2 = 58
| 58 -> 5^2 + 8^2 = 89
| 89 -> 8^2 + 9^2 = 145
| 145 -> 1^2 + 4^2 + 5^2 = 42
| 42 -> 4^2 + 2^2 = 20
| 20 -> 2^2 + 0^2 = 4
| 4 -> 4^2 = 16
+------16
As we can see, the process loops infinitely between 16 and 4 and never reaches 1. So, 15 is a sad number.
Following this rule, we can find more sad numbers, such as 4, 6, 11, 20, etc.
3. Implementing the Check Method
Now that we understand how a happy number is defined, let’s implement Java methods to check whether a given number is a happy number.
A number is sad if the sequence, which each sum of the digits’ square forms, contains a loop. In other words, given a number, if one step’s calculation result already exists in the sequence, it’s a sad number.
We can utilize a HashSet data structure to implement this logic in Java. This allows us to store each step’s result and efficiently check whether a newly calculated result already exists in the set:
class HappyNumberDecider {
public static boolean isHappyNumber(int n) {
Set<Integer> checkedNumbers = new HashSet<>();
while (true) {
n = sumDigitsSquare(n);
if (n == 1) {
return true;
}
if (checkedNumbers.contains(n)) {
return false;
}
checkedNumbers.add(n);
}
}
// ...
}
As the code above shows, the sumDigitsSquare() method performs the actual calculation and returns the result:
private static int sumDigitsSquare(int n) {
int squareSum = 0;
while (n != 0) {
squareSum += (n % 10) * (n % 10);
n /= 10;
}
return squareSum;
}
Next, let’s create a test to verify whether our isHappyNumber() method reports the expected result for different inputs:
assertTrue(HappyNumberDecider.isHappyNumber(7));
assertTrue(HappyNumberDecider.isHappyNumber(10));
assertTrue(HappyNumberDecider.isHappyNumber(13));
assertTrue(HappyNumberDecider.isHappyNumber(19));
assertTrue(HappyNumberDecider.isHappyNumber(23));
assertFalse(HappyNumberDecider.isHappyNumber(4));
assertFalse(HappyNumberDecider.isHappyNumber(6));
assertFalse(HappyNumberDecider.isHappyNumber(11));
assertFalse(HappyNumberDecider.isHappyNumber(15));
assertFalse(HappyNumberDecider.isHappyNumber(20));
First, let’s analyze the solution’s time complexity.
Let’s say we have a number n with k digits. So, we need k iterations to calculate the sum of digit squares. Further, since k = log n (logarithm at base 10), O(log n) is the time complexity for calculating the first result. Let’s call it result1. As the maximum digit is 9, the maximum value of result1 is 9^2 * log n.
If result1 isn’t 1, we must repeat calling sumDigitsSquare(). Then, the time complexity so far is O(log n) + O(log (9^2 * log n)) = O(log n) + O(log 81 + log log n). After removing the constant part, we get O(log n) + O(log log n).
Therefore, our total time complexity becomes O(log n) + O(log log n) + O(log log log n) + O(log log log log n) + … until a result reaches 1 or we detect a loop. As log n is the dominant part in this expression, the solution’s time complexity is O(log n).
Before we move to the space complexity analysis, let’s list the largest number n with k digits and the corresponding result1:
k Largest n result1
1 9 81
2 99 162
3 999 243
4 9999 324
5 99999 405
6 999999 486
7 9999999 567
8 99999999 648
9 999999999 729
10 9999999999 810
11 99999999999 891
12 999999999999 972
13 9999999999999 1053
...
1m 9..a million..9 81000000
As we can see, given the number n with more than three digits, repeatedly applying the sumDigitsSquare() operation can rapidly decrease n to a 3-digit number within a few steps.
For example, when k=1m, n is much larger than Java’s Long.MAX_VALUE. It only takes two steps to reach a number with less than three digits: 9..(1m)..9 -> 81000000 (9^2 * 1m = 81000000) -> 65 (8^2 + 1^2 = 65)
Hence, within Java’s int or long range, it’s reasonable to assume that n requires a constant C steps to reach a number with three or fewer digits. Consequently, our HashSet holds a maximum of C+243 results, yielding a space complexity of O(1).
While the space complexity of this method is O(1), it still requires space to store results for detecting cycles.
Let’s now aim to refine the solution to identify happy numbers without using extra space.
5. Improving the isHappyNumber() Method
Floyd’s cycle detection algorithm can detect cycles in a sequence. For example, we can apply this algorithm to check if a LinkedList contains a circle.
The idea is to maintain two-pointers, slow and fast. slow gets updated one step at a time, and fast is replaced every two steps. If they meet at 1, the given number is happy. Otherwise, if they meet but the value isn’t 1, a cycle is detected. Thus, the given number is sad.
Next, let’s implement the slow-fast logic in Java:
public static boolean isHappyNumberFloyd(int n) {
int slow = n;
int fast = n;
do {
slow = sumDigitsSquare(slow);
fast = sumDigitsSquare(sumDigitsSquare(fast));
} while (slow != fast);
return slow == 1;
}
Let’s test the isHappyNumberFloyd() method with the same inputs:
assertTrue(HappyNumberDecider.isHappyNumberFloyd(7));
assertTrue(HappyNumberDecider.isHappyNumberFloyd(10));
assertTrue(HappyNumberDecider.isHappyNumberFloyd(13));
assertTrue(HappyNumberDecider.isHappyNumberFloyd(19));
assertTrue(HappyNumberDecider.isHappyNumberFloyd(23));
assertFalse(HappyNumberDecider.isHappyNumberFloyd(4));
assertFalse(HappyNumberDecider.isHappyNumberFloyd(6));
assertFalse(HappyNumberDecider.isHappyNumberFloyd(11));
assertFalse(HappyNumberDecider.isHappyNumberFloyd(15));
assertFalse(HappyNumberDecider.isHappyNumberFloyd(20));
Finally, this solution’s time complexity remains O(log n). Since it requires no extra space, its space complexity is O(1).
6. Conclusion
In this article, we learned the concept of a happy number and implemented Java methods to determine whether a given number is happy.
As always, the complete source code for the examples is available over on GitHub.
