grid47 Exploring patterns and algorithms
Oct 17, 2024
6 min read
Solution to LeetCode 202: Happy Number Problem
A happy number is a number that eventually reaches 1 when replaced by the sum of the squares of its digits. If the process results in an endless loop of numbers, the number is not happy. Your task is to determine whether a given number is a happy number.
Problem
Approach
Steps
Complexity
Input: The input consists of a positive integer n, where 1 <= n <= 231 - 1.
Example: n = 23
Constraints:
• 1 <= n <= 231 - 1
Output: Return true if the number n is a happy number, otherwise return false.
Example: Output: false
Constraints:
• The output should be a boolean value indicating whether the number is happy or not.
Goal: The goal is to check if the number n becomes 1 by repeatedly replacing it with the sum of the squares of its digits, or if it falls into an endless loop.
Steps:
• Create a helper function to calculate the sum of the squares of the digits of a number.
• Use the Floyd's Cycle detection algorithm (also known as the slow and fast pointers technique) to detect if the number falls into a cycle. If the number becomes 1, it's happy, otherwise it's not.
Goal: Ensure the solution works efficiently for numbers up to the given limit.
Steps:
• The number n must be a positive integer between 1 and 231 - 1.
Assumptions:
• The input number is always a valid positive integer within the given constraints.
• Input: n = 19
• Explanation: In this case, the sum of the squares of digits is 12 + 92 = 82, then 82 + 22 = 68, then 62 + 82 = 100, and 12 + 02 + 02 = 1. Since the number eventually reaches 1, it's a happy number.
• Input: n = 2
• Explanation: For n = 2, the sum of the squares of digits is 4, then 4 becomes 16, then 37, and so on. Since it falls into a cycle, it is not a happy number.
Approach: To determine if a number is happy, we use the process of repeatedly replacing the number by the sum of the squares of its digits. If the number eventually reaches 1, it's happy. If it falls into a cycle, it's not.
Observations:
• A brute force approach of tracking the numbers could be inefficient due to the potential for cycles.
• Using the Floyd's Cycle detection method is an optimal approach to detect cycles.
• Using slow and fast pointers will allow us to detect a cycle in linear time, improving efficiency.
Steps:
• Define a helper function that calculates the sum of the squares of the digits of a number.
• Initialize two pointers, slow and fast, both starting at n.
• Move the slow pointer one step at a time and the fast pointer two steps at a time by applying the sum of the squares of digits function.
• If the slow and fast pointers meet, check if the slow pointer equals 1 to determine if the number is happy.
Empty Inputs:
• Since n is always a positive integer, there will be no empty inputs.
Large Inputs:
• For large values of n, the approach should work efficiently due to the cycle detection method.
Special Values:
• The value n = 1 is trivially a happy number since it stays at 1.
Constraints:
• The solution should handle all valid inputs efficiently.
intsqr(int n) {
int res =0;
while(n) {
int tmp = n %10;
res += tmp * tmp;
n = n /10;
}
return res;
}
boolisHappy(int n) {
int slow = n;
int fast = n;
do {
slow = sqr(slow);
fast = sqr(sqr(fast));
} while(slow != fast);
return slow ==1;
}
1 : Function Definition
intsqr(int n) {
Define the function `sqr` that calculates the sum of squares of digits for a given integer.
2 : Variable Initialization
int res =0;
Initialize a variable `res` to store the sum of the squares of the digits.
3 : While Loop Condition
while(n) {
Start a while loop that continues until `n` becomes 0. This will process each digit of `n`.
4 : Extract Last Digit
int tmp = n %10;
Extract the last digit of `n` using the modulus operator.
5 : Sum of Squares of Digits
res += tmp * tmp;
Square the extracted digit and add it to `res`.
6 : Remove Last Digit
n = n /10;
Remove the last digit of `n` by performing integer division by 10.
7 : Return Result
return res;
Return the sum of the squares of the digits stored in `res`.
8 : Function Definition
boolisHappy(int n) {
Define the `isHappy` function which checks if a number `n` is a happy number by using the Tortoise and Hare algorithm.
9 : Variable Initialization
int slow = n;
Initialize `slow` pointer to `n`. It will move one step at a time.
10 : Variable Initialization
int fast = n;
Initialize `fast` pointer to `n`. It will move two steps at a time.
11 : Do While Loop
do {
Start a do-while loop to calculate the sum of squares of digits for `slow` and `fast` until they meet.
12 : Slow Pointer Update
slow = sqr(slow);
Move the `slow` pointer by calculating the sum of squares of its digits using the `sqr` function.
13 : Fast Pointer Update
fast = sqr(sqr(fast));
Move the `fast` pointer by calculating the sum of squares of its digits twice (two steps).
14 : Loop Condition
} while(slow != fast);
Repeat the loop until `slow` and `fast` pointers meet. If they meet at 1, the number is happy.
15 : Check if Happy
return slow ==1;
Return true if `slow` equals 1, indicating that `n` is a happy number. Otherwise, return false.
Best Case: O(log(n))
Average Case: O(log(n))
Worst Case: O(log(n))
Description: The time complexity is logarithmic due to the number of digits in the number n and the cycle detection method.
Best Case: O(1)
Worst Case: O(1)
Description: The space complexity is constant as we are only using a few variables for the pointers and digit calculations.
