1. Overview
1.概述
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.
在本教程中，我们将了解如何定义快乐数字，并探索如何实现一个 Java 程序来检查给定数字是否是快乐数字。
2. Understanding the Happy Number
2.了解快乐数字
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.
一个快乐的数字通过重复替换数字的平方和达到 1。相反，一个不快乐（悲伤）的数字陷入无限循环，却永远不会达到 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.
如上例所示，输入的数字 19 最终得到了 1。因此，19 是一个快乐的数字。类似地，更多快乐数字的例子还有 7、10、13、23 等。
However, if the input is 15, we’ll never reach 1:
但是，如果输入是 15，我们就永远不会达到 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.
我们可以看到，这个过程在 16 和 4 之间无限循环，从未达到 1。因此，15 是一个悲哀的数字。
Following this rule, we can find more sad numbers, such as 4, 6, 11, 20, etc.
根据这一规则，我们可以找到更多悲伤的数字，如 4、6、11、20 等。
3. Implementing the Check Method
3.实施检查法
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.
既然我们已经了解了快乐数字是如何定义的，那么让我们来实现 Java 方法，检查给定的数字是否是快乐数字。
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:
我们可以利用 HashSet 数据结构在 Java 中实现这一逻辑。这样，我们就可以存储每一步的结果，并有效地检查新计算出的结果是否已存在于集合中：
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:
如上面的代码所示，sumDigitsSquare() 方法执行实际计算并返回结果：
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:
接下来，让我们创建一个测试，以验证我们的 isHappyNumber() 方法是否会针对不同的输入报告预期的结果：
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
4.性能分析
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.
假设有一个数字 n 包含 k 个位数。因此，我们需要 k 次迭代来计算数位平方和。此外，由于 k = log n（以 10 为底的对数），计算第一个结果的时间复杂度为 O(log n)。让我们称它为 结果 1。由于最大位数是 9，result1的最大值为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).
如果 result1 不是 1，我们必须重复调用 sumDigitsSquare()。那么，到目前为止的时间复杂度为 O(log n) + O(log (9^2 * log n)) = O(log n) + O(log 81 + log log n) 。去掉常数部分后，我们得到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).
因此，我们的总时间复杂度变为 O（log n）+O（log log n）+O（log log log n）+O（log log log n）+……直到结果达到 1 或我们检测到一个循环。由于 log n是这个表达式中的主要部分，因此解决方案的时间复杂度为 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 位数的最大数字 n 以及相应的 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 81000000As 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.
我们可以看到，给定的数字 n 超过三位，重复应用 sumDigitsSquare() 操作可以在几步内将 n 快速减小到三位数。
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)
例如，当k=1m时，n比 Java 的 Long.MAX_VALUE 大得多。只需两步就能得到一个少于三位数的数字：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).
因此，在 Java 的 int 或 long 范围内，可以合理地假设 n 需要恒定的 C 步数才能得到三位或更少的数字。因此，我们的 HashSet 最多可保存 C+243 个结果，空间复杂度为 O(1) 。
While the space complexity of this method is O(1), it still requires space to store results for detecting cycles.
虽然这种方法的空间复杂度为 O(1)，但仍需要空间来存储检测循环的结果。
Let’s now aim to refine the solution to identify happy numbers without using extra space.
现在，让我们改进解决方案，在不占用额外空间的情况下识别快乐数字。
5. Improving the isHappyNumber() Method
5.改进 isHappyNumber() 方法
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.
Floyd 循环检测算法可以检测序列中的循环。例如，我们可以应用此算法来检查 LinkedList 是否包含一个圆。
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.
我们的想法是维护两个指针，即 slow 和 fast。慢每次更新一步，而快每两步被替换一次。如果它们在 1 处相遇，给定的数字就是快乐的。否则，如果它们相遇但值不是 1，就会检测到一个循环。因此，给定的数字是悲伤的。
Next, let’s implement the slow-fast logic in Java:
接下来，让我们用 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:
让我们使用相同的输入来测试 isHappyNumberFloyd() 方法：
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).
最后，该解决方案的时间复杂度仍为 O（log n）。由于不需要额外空间，其空间复杂度为 O(1)。
6. Conclusion
6.结论
In this article, we learned the concept of a happy number and implemented Java methods to determine whether a given number is happy.
在本文中，我们学习了快乐数字的概念，并实现了 Java 方法来确定给定数字是否快乐。
As always, the complete source code for the examples is available over on GitHub.
与往常一样，这些示例的完整源代码可在 GitHub 上获取。