Check if a Number Is a Happy Number in Java

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));

4. Performance Analysis

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.