LeetCode 202 - Happy Number(cycle detection)
Read question here: https://leetcode.com/problems/happy-number/
Solution:
class Solution {
public boolean isHappy(int n) {
int slow = squaredSum(n);
int fast = squaredSum(squaredSum(n));
while (slow != fast) {
slow = squaredSum(slow);
fast = squaredSum(squaredSum(fast));
}
return slow == 1;
}
private int squaredSum(int n) {
int sum = 0;
while (n > 0) {
sum += Math.pow(n % 10, 2);
n /= 10;
}
return sum;
}
}
Explanation:
This problem is a classic example of a cycle detection problem. The objective is to determine if a sequence of numbers has a repeating pattern, which can be detected by keeping track of the numbers we have already seen and checking if we encounter a number that we have seen before.
The given code uses a cycle detection algorithm called Floyd's cycle-finding algorithm, also known as the "tortoise and hare" algorithm. The algorithm works by using two pointers, one that moves at a slower pace than the other. In this code,
slowandfastare the two pointers.The algorithm starts by initializing
slowandfastto the squared sum of the input numbernand the squared sum of the squared sum ofn, respectively. Then, it enters a loop where it repeatedly updatesslowandfastby calculating the squared sum of their current values untilslowandfastare equal.If
slowandfastare equal, it means that we have found a cycle, and we break out of the loop. Otherwise, we continue updatingslowandfast. Finally, we check ifslowis equal to 1. If it is, the input numbernis a happy number and we returntrue. Otherwise,nis not a happy number and we returnfalse.
My concern:
I have 2 concerns one is: is while loop always has a cycle? and the second is: why isHappy function always return slow == 1, and what it does mean?
Great questions!
Regarding your first concern, the while loop in the given code may not always have a cycle. If the input number n is a happy number, then the loop will terminate when slow becomes 1, and there will be no cycle. However, if n is not a happy number, then the loop will eventually enter a cycle, and the while loop will continue indefinitely until the cycle is detected and the loop is broken.
In other words, the while loop in the given code may or may not have a cycle, depending on the input number n. The cycle detection algorithm is used to handle cases where a cycle exists.
Regarding your second concern, the isHappy function returns true if the input number n is a happy number, and false otherwise. The slow == 1 check is used to determine if the squared sum of the digits of n eventually results in 1, which is the condition for a number to be considered happy.
The cycle detection algorithm is used to handle cases where the squared sum of the digits of n does not result in 1, but instead enters a cycle. If a cycle is detected, the while loop will continue indefinitely until the cycle is detected, and the slow pointer will eventually point to a number that has already been seen before in the cycle. At this point, the squared sum of the digits of n will continue to generate the same sequence of numbers in the cycle, and will never reach 1. Therefore, the function returns false in this case, indicating that the input number n is not a happy number.
If the while loop terminates because slow becomes 1, it means that the squared sum of the digits of n eventually results in 1, and the input number n is a happy number. Therefore, the function returns true.
In summary, the slow == 1 check in the isHappy function is used to determine if the input number n is a happy number, and the cycle detection algorithm is used to handle cases where a cycle exists in the squared sum of the digits of n.
Here is a list of some common algorithms that are used in computer science and software engineering, including Floyd's cycle detection algorithm:
Binary search
Depth-first search (DFS)
Breadth-first search (BFS)
Dijkstra's algorithm
Floyd's cycle detection algorithm
Knapsack problem algorithms
Traveling salesman problem algorithms
Shortest path algorithms
Minimum spanning tree algorithms
Maximum flow algorithms
Backtracking
Branch and bound
Monte Carlo algorithms
Las Vegas algorithms
Randomized algorithms
Approximation algorithms
Hashing algorithms
Famous one :
Binary search: A search algorithm that works by repeatedly dividing the search interval in half.
Sorting algorithms: Algorithms that rearrange elements in a list or array in a particular order, such as quicksort, merge sort, insertion sort, and bubble sort.
Dynamic programming: A technique for solving problems by breaking them down into smaller subproblems, solving each subproblem once, and storing the solution to each subproblem so that it can be used to solve larger problems.
Divide and conquer: A technique for solving problems by breaking them down into smaller subproblems, solving each subproblem independently, and then combining the solutions to the subproblems to solve the original problem.
Greedy algorithms: Algorithms that make locally optimal choices at each step in the hope of finding a global optimum.
Recursion: A technique for solving problems by breaking them down into smaller subproblems that are solved recursively, until a base case is reached.
Backtracking: A technique for finding all (or some) solutions to a problem that incrementally builds candidates to the solutions, and abandons a candidate ("backtracks") as soon as it determines that the candidate cannot possibly be completed to a valid solution.
Hash tables: Data structures that allow efficient insertion, deletion, and lookup of key-value pairs.
Graph algorithms: Algorithms that operate on graphs, such as breadth-first search, depth-first search, Dijkstra's algorithm, and Kruskal's algorithm.
Memoization: A technique for optimizing dynamic programming algorithms by storing the results of expensive function calls and returning the cached result when the same inputs occur again.
Do like it if you find this post helpful ♥