Happy Number - Complete Solution Guide

Happy Number is LeetCode problem 202, a Easy level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

Problem Statement

Write an algorithm to determine if a number n is happy. A happy number is a number defined by the following process: Starting with any positive integer, replace the number by the sum of the squares of its digits. Repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1. Those numbers for which this process ends in 1 are happy. Return true if n is a happy number, and false if not . Example 1: Input: n = 19 Output: true Explanatio

Detailed Explanation

The problem asks you to determine if a given positive integer is a 'happy number'. A happy number is defined by iteratively summing the squares of its digits. If this process eventually leads to the number 1, it's a happy number; otherwise, it's not (it will enter an infinite loop). The input is a positive integer `n`, and the output is a boolean value (true if `n` is happy, false otherwise).

Solution Approach

The Python and Java solutions use a set to track the numbers encountered during the iterative process. The algorithm continues until either the number becomes 1 or a previously seen number is encountered (indicating a cycle). The C++ and C solutions utilize Floyd's cycle-finding algorithm (Tortoise and Hare). This approach uses two pointers, a 'slow' pointer and a 'fast' pointer, moving at different speeds through the sequence of numbers generated. If a cycle exists, the two pointers will eventually meet; otherwise, the fast pointer will eventually reach 1.

Step-by-Step Algorithm

1. Initialize a set (Python/Java) to store visited numbers, or initialize two integer variables, `slow` and `fast` (C++/C).
2. Enter a `while` loop (or `do-while` loop in C++/C). The loop condition checks if the number is not 1 and has not been seen before (Python/Java) or if the slow and fast pointers are not equal (C++/C).
3. Calculate the sum of the squares of the digits of the current number. (This is done differently in the C++ and C solutions using a helper function).
4. Update the number (Python/Java) or the `slow` and `fast` pointers (C++/C). The fast pointer moves twice as fast as the slow pointer in C++/C.
5. If the number becomes 1 (Python/Java) or the `slow` pointer equals 1 (C++/C), return `true`. Otherwise, if a previously seen number is encountered (Python/Java) or the `slow` and `fast` pointers are equal (C++/C), return `false`.
6. Repeat steps 3-5 until the loop condition is false.

Key Insights

• The process of summing the squares of digits can lead to cycles. Detecting these cycles is crucial to avoid infinite loops.
• Using a set (or hash table) to store previously encountered numbers allows for efficient cycle detection.
• Floyd's Tortoise and Hare algorithm (used in the C++ and C solutions) provides a more efficient way to detect cycles without explicitly storing all visited numbers.

Complexity Analysis

Time Complexity: O(log n)

Space Complexity: O(log n)

Topics

This problem involves: Hash Table, Math, Two Pointers.

Companies

Asked at: Accenture, Airbnb, BlackRock, Cisco, Cognizant, FactSet, IBM, J.P. Morgan, Jump Trading, Nike, PayPal, Snowflake, Swiggy, Verily, X, Zoho, tcs.