Jobs

Interviews

Discussions

Happy Number

Easy

Verily

1 view

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

Happy Number

Easy

Verily

1 view

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

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?
Can the input integer n be negative or zero?
If the process enters a loop that does not include 1, how many iterations should I perform before concluding it's not a happy number and returning false?
Is there a theoretical maximum number of iterations needed to determine if a number is happy, and if so, what is it?
Are we concerned about potential integer overflow when calculating the sum of squares of digits for very large numbers?

Brute Force Solution

Approach

We want to determine if a number is happy by repeatedly summing the squares of its digits. The brute force approach involves simply following this process for a number and keeping track of the numbers we've seen to avoid getting stuck in a cycle.

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 this sum is equal to 1. If it is, the number is happy, and we're done.
If the sum is not 1, check if we have already seen this sum before. This is crucial for detecting cycles.
If we have seen the sum before, it means we are in a loop and the number is not happy, and we're done.
If we haven't seen the sum before, remember this sum and repeat the process using this sum as the new starting number.

Code Implementation

def is_happy_number(number):    seen_numbers = set()
    while True:
        sum_of_squared_digits = 0
        temporary_number = number
        
        while temporary_number > 0:
            digit = temporary_number % 10
            sum_of_squared_digits += digit ** 2
            temporary_number //= 10

        if sum_of_squared_digits == 1:
            return True

        # Check to see if we have found a loop
        if sum_of_squared_digits in seen_numbers:
            return False

        # Adding the current sum to seen numbers set
        seen_numbers.add(sum_of_squared_digits)

        number = sum_of_squared_digits

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(log n) – The runtime complexity is O(log n) because the number of digits in the number reduces with each iteration, and the number of iterations it takes to reach 1 or enter a cycle is logarithmic with respect to the input number n. The set lookup operation has an average time complexity of O(1), so the dominant factor is the number of iterations, which grows logarithmically with n.

Space Complexity

O(N) – The algorithm stores previously seen sums to detect cycles. In the worst-case scenario, before encountering either 1 or a cycle, the algorithm may encounter and store a number of distinct sums proportional to the number of digits in the initial input number, N. This 'seen' set will therefore use space proportional to N. Thus, the auxiliary space complexity is O(N).

Optimal Solution

Approach

The key idea is to recognize that if a number is not happy, the process will eventually enter a cycle. We can detect this cycle by remembering numbers we've already seen. If we encounter a number we've seen before, we know we're in a cycle and the number is not happy.

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 this new sum is equal to 1. If so, the number is happy, and we're done.
If the sum is not 1, check if we've already seen this sum before. We can use a 'memory' or record of sums we've calculated.
If we've seen the sum before, it means we're in a loop, and the number is not happy. We are done.
If we haven't seen the sum before, add it to our memory and repeat steps 2-5 using this sum as the new number.

Code Implementation

def is_happy(number):
    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

        # If we've seen this number before, it's a cycle.
        if sum_of_squared_digits in seen_numbers:
            return False

        # Store the number to detect cycles.
        seen_numbers.add(sum_of_squared_digits)

        number = sum_of_squared_digits

    return True

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(log n) – The time complexity is determined by how many iterations it takes to either reach 1 or enter a cycle. Each iteration involves calculating the sum of squares of digits. The number of digits in n is proportional to log(n). In the worst case, it may take a few iterations to reach 1 or a repeating cycle, but the number of iterations is still related to the number of digits, which is logarithmic. Therefore, the overall time complexity can be approximated as O(log n).

Space Complexity

O(1) – The algorithm uses a set (or similar data structure described as 'memory' in the plain English explanation) to store the sums that have already been encountered. In the worst-case scenario, before the sequence either reaches 1 or enters a cycle, the set might store a number of sums. However, the values are capped, as the largest sum we can get from squaring the digits is bounded by the number of digits in N, and therefore, the sums are also bounded. The space used by the set, therefore, grows very slowly, and practically, we consider the memory usage to be constant regardless of the input number N. Hence the space complexity is O(1).

Edge Cases

Case	How to Handle
Input is a negative number	Return false immediately as the problem specifies a process starting with the input number, and the squaring of negative digits will eventually lead to the same number sequence as its positive counterpart, if the positive counter part ends up in an infinite loop.
Input is zero	Return false because the sum of squares of digits will remain zero and never reach 1.
Input is 1	Return true immediately because the number is already 1.
Large input that potentially causes integer overflow when squaring the digits	Use a data type with a larger range to avoid overflow or apply modulo operation if needed, but in this problem, the sum of squares of digits reduces the integer, so it wont overflow.
Number leads to a cycle not including 1	Use a set to store previously seen numbers and return false if the current number is already in the set.
Single-digit number other than 1	The sum of squares will be the square of the number, so using the cycle detection mechanism by set will cause it to terminate if it isn't 1.
Number with many digits which could increase space complexity if cycle detection is inefficient	Cycle detection should be efficient (e.g., using a hash set), as even very large numbers will quickly reduce to smaller numbers.
Very large number of iterations before a cycle is found or 1 is reached	Cycle detection is still crucial to prevent infinite loops, regardless of the iteration count.

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?
Can the input integer n be negative or zero?
If the process enters a loop that does not include 1, how many iterations should I perform before concluding it's not a happy number and returning false?
Is there a theoretical maximum number of iterations needed to determine if a number is happy, and if so, what is it?
Are we concerned about potential integer overflow when calculating the sum of squares of digits for very large numbers?

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.
Check if this sum is equal to 1. If it is, the number is happy, and we're done.
If the sum is not 1, check if we have already seen this sum before. This is crucial for detecting cycles.
If we have seen the sum before, it means we are in a loop and the number is not happy, and we're done.
If we haven't seen the sum before, remember this sum and repeat the process using this sum as the new starting number.

Code Implementation

def is_happy_number(number):    seen_numbers = set()
    while True:
        sum_of_squared_digits = 0
        temporary_number = number
        
        while temporary_number > 0:
            digit = temporary_number % 10
            sum_of_squared_digits += digit ** 2
            temporary_number //= 10

        if sum_of_squared_digits == 1:
            return True

        # Check to see if we have found a loop
        if sum_of_squared_digits in seen_numbers:
            return False

        # Adding the current sum to seen numbers set
        seen_numbers.add(sum_of_squared_digits)

        number = sum_of_squared_digits

Try it yourself on LeetCode

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 this new sum is equal to 1. If so, the number is happy, and we're done.
If the sum is not 1, check if we've already seen this sum before. We can use a 'memory' or record of sums we've calculated.
If we've seen the sum before, it means we're in a loop, and the number is not happy. We are done.
If we haven't seen the sum before, add it to our memory and repeat steps 2-5 using this sum as the new number.

Code Implementation

def is_happy(number):
    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

        # If we've seen this number before, it's a cycle.
        if sum_of_squared_digits in seen_numbers:
            return False

        # Store the number to detect cycles.
        seen_numbers.add(sum_of_squared_digits)

        number = sum_of_squared_digits

    return True

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Input is a negative number	Return false immediately as the problem specifies a process starting with the input number, and the squaring of negative digits will eventually lead to the same number sequence as its positive counterpart, if the positive counter part ends up in an infinite loop.
Input is zero	Return false because the sum of squares of digits will remain zero and never reach 1.
Input is 1	Return true immediately because the number is already 1.
Large input that potentially causes integer overflow when squaring the digits	Use a data type with a larger range to avoid overflow or apply modulo operation if needed, but in this problem, the sum of squares of digits reduces the integer, so it wont overflow.
Number leads to a cycle not including 1	Use a set to store previously seen numbers and return false if the current number is already in the set.
Single-digit number other than 1	The sum of squares will be the square of the number, so using the cycle detection mechanism by set will cause it to terminate if it isn't 1.
Number with many digits which could increase space complexity if cycle detection is inefficient	Cycle detection should be efficient (e.g., using a hash set), as even very large numbers will quickly reduce to smaller numbers.
Very large number of iterations before a cycle is found or 1 is reached	Cycle detection is still crucial to prevent infinite loops, regardless of the iteration count.