Jobs

Interviews

Discussions

Happy Number

Easy

Amazon

3 views

Topics:

RecursionTwo Pointers

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
Explanation:
1^2 + 9^2 = 82
8^2 + 2^2 = 68
6^2 + 8^2 = 100
1^2 + 0^2 + 0^2 = 1

Example 2:

Input: n = 2
Output: false

Constraints:

1 <= n <= 2^31 - 1

Happy Number

Easy

Amazon

3 views

Topics:

RecursionTwo Pointers

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
Explanation:
1^2 + 9^2 = 82
8^2 + 2^2 = 68
6^2 + 8^2 = 100
1^2 + 0^2 + 0^2 = 1

Example 2:

Input: n = 2
Output: false

Constraints:

1 <= n <= 2^31 - 1

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of possible values for the input integer n?
Are we guaranteed that n will always be a positive integer?
If the number is not happy (i.e., it falls into a cycle), how long should the algorithm run before returning false? Is there a defined limit?
Can you provide an example of an input that is not a happy number?
Is there a specific data structure (e.g., a hash set) I should use to detect cycles, or is any cycle detection method acceptable?

Brute Force Solution

Approach

The brute force approach to determining if a number is a happy number is to repeatedly calculate the sum of the squares of its digits. We continue this process, checking if we reach 1 (meaning it's a happy number) or if we enter a cycle (meaning it's not).

Here's how the algorithm would work step-by-step:

Start with the given number.
Calculate the sum of the squares of its digits to get a new number.
Repeat the process with the new number.
Keep track of all the numbers you've seen so far.
If at any point you reach the number 1, the original number is a happy number.
If at any point you encounter a number you've seen before, you're in a loop, and the original number is not a happy number.
If you haven't found 1 or a loop after a reasonable number of steps, you can assume the number is not happy.

Code Implementation

def is_happy_number(number):
    seen_numbers = set()

    while number != 1:
        # Check if we've entered a cycle.
        if number in seen_numbers:
            return False

        seen_numbers.add(number)

        sum_of_squared_digits = 0
        temporary_number = number

        # Calculate the sum of squared digits.
        while temporary_number > 0:
            digit = temporary_number % 10
            sum_of_squared_digits += digit ** 2
            temporary_number //= 10

        number = sum_of_squared_digits

    return True

Big(O) Analysis

Time Complexity

O(log n) – The time complexity is determined by how many iterations are needed to reach 1 or enter a cycle. The input size n, which is the initial number, shrinks significantly in each iteration because we are summing the squares of the digits. The number of iterations required is logarithmic with respect to n because the number decreases rapidly. Detecting the cycle takes constant time O(1) using a hash set. Therefore, the overall time complexity is O(log n).

Space Complexity

O(log N) – The algorithm keeps track of numbers it has seen in a set. In the worst-case scenario, the numbers generated before encountering either 1 or a cycle could grow proportionally to the number of digits in the original number N. The number of digits is proportional to log N (base 10). Therefore, the space used to store these numbers grows proportionally to the number of digits, which is log N. Thus, the space complexity is O(log N).

Optimal Solution

Approach

A happy number eventually reaches 1 after repeatedly replacing it with the sum of the squares of its digits. The optimal approach detects cycles to avoid infinite loops and determine if a number is happy efficiently.

Here's how the algorithm would work step-by-step:

Start with the given number.
Calculate the sum of the squares of its digits.
Check if the new number is 1. If it is, the original number is happy, and we're done.
If the new number is not 1, check if we've seen it before. We need to keep track of all the numbers we've encountered during our calculations.
If we've seen the number before, it means we're in a loop, and the original number is not happy. Stop here.
If we haven't seen the number before, remember it and repeat the process with this new number.

Code Implementation

def is_happy(number) -> bool:
    seen_numbers = set()

    while number != 1:
        sum_of_squared_digits = 0
        temp_number = number

        while temp_number > 0:
            digit = temp_number % 10
            sum_of_squared_digits += digit ** 2
            temp_number //= 10

        number = sum_of_squared_digits

        # Cycle detection to identify unhappy numbers
        if number in seen_numbers:
            return False

        # Keep track of checked numbers.
        seen_numbers.add(number)

    # If the number eventually becomes 1
    return True

Big(O) Analysis

Time Complexity

O(log n) – The time complexity is O(log n) because the number of digits in the input number 'n' roughly halves after each iteration (sum of squares operation). While calculating the sum of squares involves iterating through the digits, the number of digits is logarithmic with respect to the initial number. The 'seen' set operations (checking for and inserting) take near constant time on average. The process continues until either the number becomes 1 (happy number) or a cycle is detected, both of which typically occur within a logarithmic number of iterations relative to the initial input number.

Space Complexity

O(N) – The algorithm uses a set (or similar data structure) to keep track of numbers encountered during the calculation, as described in steps 4 and 5. In the worst-case scenario, the algorithm might encounter a significant number of different numbers before either reaching 1 or entering a cycle. The size of this set can grow up to N, where N is related to the initial number and the numbers generated during the process until a cycle is detected or 1 is reached. Therefore, the auxiliary space used by the algorithm is O(N).

Edge Cases

Case	How to Handle
Input is zero	Return false, since zero is not a positive integer and violates problem conditions.
Input is 1	Return true immediately as 1 is already a happy number by definition.
Input is a very large number that potentially causes an infinite loop	Use a set to track previously seen numbers and return false if a number repeats, indicating a cycle.
Input results in a very long sequence of sums before either reaching 1 or a cycle	The set tracking ensures that long sequences are handled without exceeding memory limits significantly.
Integer overflow when squaring digits of a large number.	Consider using a larger integer type if the sum of squares could exceed the maximum value of the default integer type, or modular arithmetic if appropriate.
Negative Input	Return false, since the problem specifies a positive integer.
The input consists of all 9s (e.g., 99999)	This tests the performance with a number that yields larger intermediate sums before potentially looping or resolving to 1, and the cycle detection should appropriately terminate.
Input leads to known unhappy cycles (e.g., the 4, 16, 37, 58, 89, 145, 42, 20 cycle)	The set tracking previously seen numbers should correctly identify and handle these cycles.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of possible values for the input integer n?
Are we guaranteed that n will always be a positive integer?
If the number is not happy (i.e., it falls into a cycle), how long should the algorithm run before returning false? Is there a defined limit?
Can you provide an example of an input that is not a happy number?
Is there a specific data structure (e.g., a hash set) I should use to detect cycles, or is any cycle detection method acceptable?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Start with the given number.
Calculate the sum of the squares of its digits to get a new number.
Repeat the process with the new number.
Keep track of all the numbers you've seen so far.
If at any point you reach the number 1, the original number is a happy number.
If at any point you encounter a number you've seen before, you're in a loop, and the original number is not a happy number.
If you haven't found 1 or a loop after a reasonable number of steps, you can assume the number is not happy.

Code Implementation

def is_happy_number(number):
    seen_numbers = set()

    while number != 1:
        # Check if we've entered a cycle.
        if number in seen_numbers:
            return False

        seen_numbers.add(number)

        sum_of_squared_digits = 0
        temporary_number = number

        # Calculate the sum of squared digits.
        while temporary_number > 0:
            digit = temporary_number % 10
            sum_of_squared_digits += digit ** 2
            temporary_number //= 10

        number = sum_of_squared_digits

    return True

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Start with the given number.
Calculate the sum of the squares of its digits.
Check if the new number is 1. If it is, the original number is happy, and we're done.
If the new number is not 1, check if we've seen it before. We need to keep track of all the numbers we've encountered during our calculations.
If we've seen the number before, it means we're in a loop, and the original number is not happy. Stop here.
If we haven't seen the number before, remember it and repeat the process with this new number.

Code Implementation

def is_happy(number) -> bool:
    seen_numbers = set()

    while number != 1:
        sum_of_squared_digits = 0
        temp_number = number

        while temp_number > 0:
            digit = temp_number % 10
            sum_of_squared_digits += digit ** 2
            temp_number //= 10

        number = sum_of_squared_digits

        # Cycle detection to identify unhappy numbers
        if number in seen_numbers:
            return False

        # Keep track of checked numbers.
        seen_numbers.add(number)

    # If the number eventually becomes 1
    return True

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Input is zero	Return false, since zero is not a positive integer and violates problem conditions.
Input is 1	Return true immediately as 1 is already a happy number by definition.
Input is a very large number that potentially causes an infinite loop	Use a set to track previously seen numbers and return false if a number repeats, indicating a cycle.
Input results in a very long sequence of sums before either reaching 1 or a cycle	The set tracking ensures that long sequences are handled without exceeding memory limits significantly.
Integer overflow when squaring digits of a large number.	Consider using a larger integer type if the sum of squares could exceed the maximum value of the default integer type, or modular arithmetic if appropriate.
Negative Input	Return false, since the problem specifies a positive integer.
The input consists of all 9s (e.g., 99999)	This tests the performance with a number that yields larger intermediate sums before potentially looping or resolving to 1, and the cycle detection should appropriately terminate.
Input leads to known unhappy cycles (e.g., the 4, 16, 37, 58, 89, 145, 42, 20 cycle)	The set tracking previously seen numbers should correctly identify and handle these cycles.