Jobs

Interviews

Discussions

Happy Number

#1 Most AskedEasy

Happy Number #1 Most Asked

Easy

Verily

62 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² + 9² = 82
8² + 2² = 68
6² + 8² = 100
1² + 0² + 0² = 1

Example 2:

Input: n = 2
Output: false

Constraints:

1 <= n <= 2³¹ - 1

Try coding it in LeetCode

Happy Number

#1 Most AskedEasy

Happy Number #1 Most Asked

Easy

Verily

62 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² + 9² = 82
8² + 2² = 68
6² + 8² = 100
1² + 0² + 0² = 1

Example 2:

Input: n = 2
Output: false

Constraints:

1 <= n <= 2³¹ - 1

Try coding it in LeetCode

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 maximum possible value for the input integer 'n'?
Are there any specific constraints on the number of iterations the process can take before we can definitively determine if it's a happy number or not?
Are there any non-positive integers (zero or negative) that I should expect as input, and if so, how should they be handled?
Could the sum of squares of digits ever overflow standard integer types for very large initial inputs?
Is there a known upper bound to the cycle length for unhappy numbers, or is it possible to have arbitrarily long cycles?

Brute Force Solution

Approach

The brute force way to solve this is to follow the number's path of transformations repeatedly and see where it leads. We'll keep doing this transformation until we either find the special number we're looking for, or we realize we're stuck in a repeating pattern that won't lead us there.

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

Take the starting number and calculate the sum of the squares of its digits.
Use this new sum as the next number in the sequence.
Check if this new number is the special number (which is 1). If it is, we've found our answer!
If it's not the special number, we need to see if we've encountered this number before. Imagine keeping a list of all the numbers we've seen so far.
If we've seen this number before, it means the sequence is going to repeat forever without ever reaching 1. So, the original number is not happy.
If we haven't seen this number before, add it to our list of seen numbers and go back to the first step with this new number. Keep repeating this process.

Code Implementation

def is_happy(starting_number):
    seen_numbers = set()

    current_number = starting_number

    while current_number != 1 and current_number not in seen_numbers:
        # Mark the current number as seen to detect cycles
        seen_numbers.add(current_number)

        sum_of_squares = 0
        # Calculate the sum of squares of digits
        for digit_character in str(current_number):
            digit_value = int(digit_character)
            sum_of_squares += digit_value * digit_value
        
        # Update the current number for the next iteration
        current_number = sum_of_squares

    # A number is happy if the process ends at 1
    return current_number == 1

Big(O) Analysis

Time Complexity

O(log n * k) – The number of steps taken before a cycle is detected or 1 is reached is bounded. Let's consider k as the maximum number of steps in the sequence before it repeats or reaches 1. The calculation of the sum of squares of digits for a number m takes time proportional to the number of its digits, which is approximately log10(m). Since the numbers in the sequence generally decrease or converge towards a cycle, and the maximum value of a sum of squares for a number with d digits is 81*d (for 99...9), the numbers don't grow arbitrarily large. Thus, for each of the k steps, the digit squaring operation takes at most O(log n) time, where n is the initial input number. The overall complexity is therefore O(k * log n). In practice, k is often relatively small, making this efficient.

Space Complexity

O(log n) – The primary auxiliary space is used to store the numbers encountered in the sequence to detect cycles. In the worst case, the numbers encountered will not exceed a certain bound (related to the square of the maximum possible sum of squares for a given number of digits). This bound grows logarithmically with respect to the magnitude of the input number n, as the number of digits is logarithmic. Therefore, the space complexity is O(log n).

Optimal Solution

Approach

To determine if a number is 'happy,' we repeatedly transform it by summing the squares of its digits. If this process eventually reaches 1, the number is happy. If it enters a cycle without reaching 1, it's not happy. The clever part is detecting these cycles efficiently.

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

Start with the given number.
Calculate a new number by taking each digit of the current number, squaring it, and adding all those squared values together.
Keep track of all the numbers you've seen during this process.
If the new number you calculated is 1, then the original number is happy, and you're done.
Before continuing, check if you've already seen this new number before. If you have, it means you've entered a repeating pattern that doesn't include 1, so the original number is not happy, and you're done.
If the new number is not 1 and you haven't seen it before, add it to your list of seen numbers and use this new number to repeat the process from the beginning.
Continue this cycle of calculating, checking for 1, and checking for repetition until you either find 1 or detect a repeat.

Code Implementation

def is_happy_number(starting_number):
    seen_numbers = set()

    current_number = starting_number

    while current_number != 1:
        # Detect cycles to prevent infinite loops when a number is not happy.
        if current_number in seen_numbers:
            return False

        # Add the current number to our history to detect future cycles.
        seen_numbers.add(current_number)

        sum_of_squared_digits = 0
        number_to_process = current_number

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

        # Update the current number for the next iteration.
        current_number = sum_of_squared_digits

    # If the loop terminates, it means we reached 1, hence the number is happy.
    return True

Big(O) Analysis

Time Complexity

O(log n) – The process of calculating the sum of squares of digits for a number n will eventually either reach 1 or enter a cycle. The maximum value a number can reach by summing squares of its digits is bounded. For a number with d digits, the maximum sum of squares is d * 9^2 = 81d. Since d is roughly log10(n), the sum of squares grows much slower than n itself. This means the numbers in the sequence decrease quite rapidly until they become small. The number of steps to reach a cycle or 1 is logarithmic with respect to the input number n. Therefore, the time complexity is O(log n).

Space Complexity

O(log n) – The primary auxiliary space is used by a set to keep track of previously encountered numbers during the digit-squaring process. While theoretically the sequence of happy numbers could grow large, the maximum value a number can reach is bounded. The values tend to converge or enter cycles relatively quickly. Therefore, the maximum number of distinct values stored in the set before detecting a cycle or reaching 1 is not directly proportional to the input number N itself, but rather related to the maximum possible sum of squares of digits for numbers encountered, which is significantly less than N and grows very slowly, effectively making the space complexity closer to logarithmic with respect to the input number's magnitude.

Edge Cases

Case	How to Handle
Input is 1	The number 1 is already the target happy number, so the function should return true immediately.
Input is a single-digit number other than 1	Single-digit numbers will eventually lead to a cycle, and the algorithm should correctly detect this and return false.
Input causes a long sequence before reaching 1 or a cycle	The algorithm should be efficient enough to handle numbers that require many iterations without timing out.
Input enters a known cycle that does not include 1	A mechanism to detect repeated numbers in the sequence is crucial to identify non-happy numbers and avoid infinite loops.
Extremely large input numbers	While the problem statement mentions positive integers, extremely large inputs could potentially lead to integer overflow if intermediate sums of squares exceed the language's integer limits.
All digits are the same (e.g., 222, 333)	These inputs should be processed normally; the algorithm should correctly sum the squares of their digits and proceed.
Numbers that result in a 0 after summing squares of digits	This scenario is impossible for positive integers since the square of any digit (0-9) is non-negative, and at least one digit must be non-zero for a positive integer.
Input with leading zeros (e.g., 007)	Input validation or standard integer parsing should handle this by treating it as a standard integer (e.g., 7).

Input is 1

How to Handle:

The number 1 is already the target happy number, so the function should return true immediately.

Input is a single-digit number other than 1

How to Handle:

Single-digit numbers will eventually lead to a cycle, and the algorithm should correctly detect this and return false.

Input causes a long sequence before reaching 1 or a cycle

How to Handle:

The algorithm should be efficient enough to handle numbers that require many iterations without timing out.

Input enters a known cycle that does not include 1

How to Handle:

A mechanism to detect repeated numbers in the sequence is crucial to identify non-happy numbers and avoid infinite loops.

Extremely large input numbers

How to Handle:

While the problem statement mentions positive integers, extremely large inputs could potentially lead to integer overflow if intermediate sums of squares exceed the language's integer limits.

All digits are the same (e.g., 222, 333)

How to Handle:

These inputs should be processed normally; the algorithm should correctly sum the squares of their digits and proceed.

Numbers that result in a 0 after summing squares of digits

How to Handle:

This scenario is impossible for positive integers since the square of any digit (0-9) is non-negative, and at least one digit must be non-zero for a positive integer.

Input with leading zeros (e.g., 007)

How to Handle:

Input validation or standard integer parsing should handle this by treating it as a standard integer (e.g., 7).

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 maximum possible value for the input integer 'n'?
Are there any specific constraints on the number of iterations the process can take before we can definitively determine if it's a happy number or not?
Are there any non-positive integers (zero or negative) that I should expect as input, and if so, how should they be handled?
Could the sum of squares of digits ever overflow standard integer types for very large initial inputs?
Is there a known upper bound to the cycle length for unhappy numbers, or is it possible to have arbitrarily long cycles?

Brute Force Solution

Approach

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

Take the starting number and calculate the sum of the squares of its digits.
Use this new sum as the next number in the sequence.
Check if this new number is the special number (which is 1). If it is, we've found our answer!
If it's not the special number, we need to see if we've encountered this number before. Imagine keeping a list of all the numbers we've seen so far.
If we've seen this number before, it means the sequence is going to repeat forever without ever reaching 1. So, the original number is not happy.
If we haven't seen this number before, add it to our list of seen numbers and go back to the first step with this new number. Keep repeating this process.

Code Implementation

def is_happy(starting_number):
    seen_numbers = set()

    current_number = starting_number

    while current_number != 1 and current_number not in seen_numbers:
        # Mark the current number as seen to detect cycles
        seen_numbers.add(current_number)

        sum_of_squares = 0
        # Calculate the sum of squares of digits
        for digit_character in str(current_number):
            digit_value = int(digit_character)
            sum_of_squares += digit_value * digit_value
        
        # Update the current number for the next iteration
        current_number = sum_of_squares

    # A number is happy if the process ends at 1
    return current_number == 1

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 a new number by taking each digit of the current number, squaring it, and adding all those squared values together.
Keep track of all the numbers you've seen during this process.
If the new number you calculated is 1, then the original number is happy, and you're done.
Before continuing, check if you've already seen this new number before. If you have, it means you've entered a repeating pattern that doesn't include 1, so the original number is not happy, and you're done.
If the new number is not 1 and you haven't seen it before, add it to your list of seen numbers and use this new number to repeat the process from the beginning.
Continue this cycle of calculating, checking for 1, and checking for repetition until you either find 1 or detect a repeat.

Code Implementation

def is_happy_number(starting_number):
    seen_numbers = set()

    current_number = starting_number

    while current_number != 1:
        # Detect cycles to prevent infinite loops when a number is not happy.
        if current_number in seen_numbers:
            return False

        # Add the current number to our history to detect future cycles.
        seen_numbers.add(current_number)

        sum_of_squared_digits = 0
        number_to_process = current_number

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

        # Update the current number for the next iteration.
        current_number = sum_of_squared_digits

    # If the loop terminates, it means we reached 1, hence the number is happy.
    return True

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Input is 1	The number 1 is already the target happy number, so the function should return true immediately.
Input is a single-digit number other than 1	Single-digit numbers will eventually lead to a cycle, and the algorithm should correctly detect this and return false.
Input causes a long sequence before reaching 1 or a cycle	The algorithm should be efficient enough to handle numbers that require many iterations without timing out.
Input enters a known cycle that does not include 1	A mechanism to detect repeated numbers in the sequence is crucial to identify non-happy numbers and avoid infinite loops.
Extremely large input numbers	While the problem statement mentions positive integers, extremely large inputs could potentially lead to integer overflow if intermediate sums of squares exceed the language's integer limits.
All digits are the same (e.g., 222, 333)	These inputs should be processed normally; the algorithm should correctly sum the squares of their digits and proceed.
Numbers that result in a 0 after summing squares of digits	This scenario is impossible for positive integers since the square of any digit (0-9) is non-negative, and at least one digit must be non-zero for a positive integer.
Input with leading zeros (e.g., 007)	Input validation or standard integer parsing should handle this by treating it as a standard integer (e.g., 7).

Input is 1

How to Handle:

The number 1 is already the target happy number, so the function should return true immediately.

Input is a single-digit number other than 1

How to Handle:

Single-digit numbers will eventually lead to a cycle, and the algorithm should correctly detect this and return false.

Input causes a long sequence before reaching 1 or a cycle

How to Handle:

The algorithm should be efficient enough to handle numbers that require many iterations without timing out.

Input enters a known cycle that does not include 1

How to Handle:

A mechanism to detect repeated numbers in the sequence is crucial to identify non-happy numbers and avoid infinite loops.

Extremely large input numbers

How to Handle:

While the problem statement mentions positive integers, extremely large inputs could potentially lead to integer overflow if intermediate sums of squares exceed the language's integer limits.

All digits are the same (e.g., 222, 333)

How to Handle:

These inputs should be processed normally; the algorithm should correctly sum the squares of their digits and proceed.

Numbers that result in a 0 after summing squares of digits

How to Handle:

This scenario is impossible for positive integers since the square of any digit (0-9) is non-negative, and at least one digit must be non-zero for a positive integer.

Input with leading zeros (e.g., 007)

How to Handle:

Input validation or standard integer parsing should handle this by treating it as a standard integer (e.g., 7).

0/12 Verily questions completed

0/12 completed