Leetcode 202. Happy Number
Problem Explanation
In this problem, we are given an integer as input and we need to determine if it's a "happy number". A happy number is a number that follows a certain process: Given a positive integer, we replace the number by the sum of the squares of its digits, and repeat the process until the number equals 1, at which it will stay, or it will loop endlessly in a cycle which does not include 1.
For instance, if we take the number 19.
We first find the squares of the digits of 19 which is 1 and 9. The sum of the square of the digits is 1^2 + 9^2 = 82.
We then repeat the process. The sum of the squares of 8 and 2 (from 82) is 64 + 4 = 68.
This process is repeated until we reach 1 or the sequence loops endlessly. For 68, we get the sum of the squares as 100 and finally 1. Ascii illustration of the same:
1 2 319 4| 5v 682 7| 8v 968 10| 11v 12100 13| 14v 151
Since we reach 1, 19 is a happy number.
Solution Approach
The solution makes use of the Floyd's Cycle detection algorithm (also known as the Tortoise and the Hare algorithm). The algorithm is a pointer algorithm that uses two pointers which move through the sequence at different speeds.
In the context of our problem, the "slow" pointer, or tortoise, represents the sum of squares of the digits of the given number. The "fast" pointer, or hare, represents the sum of squares of the digits of the sum of squares of the digits.
The algorithm keeps moving the pointers till the slow and fast pointers meet which indicates the presence of a cycle. If the cycle is found and slow pointer points to 1, the number is a happy number. Otherwise, it's not.
Solutions
Python
1 2python 3class Solution: 4 def isHappy(self, n: int) -> bool: 5 def get_next(n): 6 return sum(int(x) ** 2 for x in str(n)) 7 8 slow = n 9 fast = get_next(n) 10 while slow != fast: 11 slow = get_next(slow) 12 fast = get_next(get_next(fast)) 13 14 return slow == 1
Java
1 2java 3class Solution { 4 public boolean isHappy(int n) { 5 int slow = n, fast = n; 6 do { 7 slow = calculate(slow); 8 fast = calculate(calculate(fast)); 9 } while (slow != fast); 10 11 return slow == 1; 12 } 13 14 private int calculate(int n) { 15 int sum = 0; 16 while (n > 0) { 17 int digit = n % 10; 18 sum += digit * digit; 19 n /= 10; 20 } 21 return sum; 22 } 23}
JavaScript
1 2javascript 3var isHappy = function(n) { 4 let slow = n, fast = n; 5 do { 6 slow = calcSquareSum(slow); 7 fast = calcSquareSum(calcSquareSum(fast)); 8 } while (slow !== fast) 9 10 return slow === 1; 11}; 12 13var calcSquareSum = function(n) { 14 let sum = 0; 15 while (n > 0) { 16 let digit = n % 10; 17 sum += digit * digit; 18 n = Math.floor(n / 10); 19 } 20 return sum; 21};
C++
1 2cpp 3class Solution { 4public: 5 bool isHappy(int n) { 6 int slow = n, fast = n; 7 do { 8 slow = compute(slow); 9 fast = compute(compute(fast)); 10 } while (slow != fast); 11 return slow == 1; 12 } 13 14private: 15 int compute(int n) { 16 int sum = 0; 17 while (n) { 18 int digit = n % 10; 19 sum += digit * digit; 20 n /= 10; 21 } 22 return sum; 23 } 24};
C#
1 2csharp 3public class Solution { 4 private int GetNext(int n) { 5 int sum = 0; 6 while (n > 0) { 7 int d = n % 10; 8 n = n / 10; 9 sum += d*d; 10 } 11 return sum; 12 } 13 14 public bool IsHappy(int n) { 15 int slow = n, fast = n; 16 do { 17 slow = GetNext(slow); 18 fast = GetNext(GetNext(fast)); 19 } while (slow != fast); 20 return slow == 1; 21 } 22}
Discussion
These solutions, while written in different programming languages, follow the same basic approach. They all use a variant of the Floyd Cycle detection algorithm, looping until the fast and slow pointers meet. If they meet at 1, the original number is a happy number.
The interesting part to note is the different language syntaxes for handling digits. For example, JavaScript uses a while loop to calculate the sum of squares of digits, utilizing modulus and Math.floor() to handle division and remainders.
Python, in contrast, converts the number to a string, allowing it to iterate over each digit in the number. Each digit is converted back to an integer, squared, and the results are summed.
Java, like JavaScript, calculates the sum of squares of digits using a while loop with modulus and floor division.
Despite the language differences, the fundamental logic of the solutions remain the same, which emphasizes the cross-language versatility of the Floyd's Cycle detection algorithm. This algorithm can be a powerful tool when dealing with sequences or lists where detection of a cycle or repeating pattern is neededโwhether that be to detect a happy number, identify a cycle in a linked list, or to solve some other pertinent problem.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.