Educative: Interactive Courses for Software Developers

Statement#

Write an algorithm to determine if a number $n$ is a happy number.

We use the following process to check if a given number is a happy number:

Starting with the given number $n$ , replace the number with the sum of the squares of its digits.
Repeat the process until:
- The number equals $1$ , which will depict that the given number $n$ is a happy number.
- It enters a cycle, which will depict that the given number $n$ is not a happy number.

Return TRUE if $n$ is a happy number, and FALSE if not.

Constraints

$1 \leq$ $n$ $\leq 2^{31} - 1$

Solution#

So far, you have probably brainstormed some approaches and have an idea of how to solve this problem. Let’s explore some of these approaches and figure out which one to follow based on considerations such as time complexity and any implementation constraints.

Naive approach#

The brute force approach is to repeatedly calculate the squared sum of digits of the input number and store the computed sum in a hash set. For every calculation, we check if the sum is already present in the set. If yes, we've detected a cycle and should return FALSE. Otherwise, we add it to our hash set and continue further. If our sum converges to $1$ , we've found a happy number.

While this approach works well for small numbers, we might have to perform several computations for larger numbers to get the required result. So, it might get infeasible for such cases. The time complexity of this approach is $O( \log n)$ . The space complexity is $O(\log n)$ since we're using additional space to store our calculated sums.

Optimized approach using Fast and Slow Pointers#

An efficient approach to solve this problem is to use fast and slow pointers. We know that a unhappy number eventually gets stuck in an infinite loop. However, there is no way for our program to detect this loop and terminate, unless we keep track of the calculated sums, which requires additional space.

If we use the fast and slow pointers approach here, the fast pointer would eventually reach 1, in which case we will return TRUE. Otherwise, it would meet the slow pointer, which would mean that the two pointers are in an endless loop, and we can return FALSE.

As an example, suppose we have the number $2$ as our $n$ . This is what the infinite loop would look like:

Note: In the following section, we will gradually build the solution. Alternatively, you can skip straight to just the code.

Step-by-step solution construction#

We will start off our solution by constructing a helper function to calculate the squared sum of digits of the input number. We know that we need to isolate the digits in our number to calculate the squared sum. This can be achieved by repeatedly removing the last digit of the number and adding its squared value to the total sum.

The helper function will find the last digit of the given number by taking its modulus with $10$ . We’ll store this in a variable digit. Now, since we’ve already separated the last digit, we can get the remaining digits by dividing the number by $10$ . Lastly, we’ll store the squared sum of digit in a variable named total_sum. We’ll repeat this until our number becomes $0$ .

To understand this better, consider a number, $19$ :

First iteration

digit $= 19 \% 10 = 9$ (last digit)
number $= 19/10 = 1$ (remaining digit(s))
total_sum $= 9^2 = 81$

Second iteration

digit $= 1 \% 10 = 1$ (last digit)
number $= 1/10 = 0$ (remaining digit(s))
total_sum $= 81 + 1^2 = 82$

As the number has become $0$ , we’ll terminate our program here. The squared sum of the digits in $19$ is $82$ .

def print_string_with_markers(strn, pValue):
    out = strn[:pValue] + '«' + strn[pValue] + '»' + strn[pValue+1:]
    return out
def sum_of_squared_digits(number):  # Helper function that calculates the sum of squared digits.
    total_sum = 0
    print("\tCalculating the sum of squared digits")
    print("\tTotal sum:", total_sum)
    i = 0
    while number > 0:
        print("\tLoop iteration #", i+1)
        a = len(str(number))
        print("\t\tThe number is ", number)
        digit = number % 10
        print("\t\t", print_string_with_markers(str(number), a - 1), "Last Digit ⟶", digit)
        a = a - 1
        print("\t\tUpdating number ⟶ number/10 = ", number, "/10")
        number = number // 10
        print("\t\t\t\tThe number is now:", number)
        print("\t\tTotal sum + square of the digit = ", total_sum, "+", digit, "*", digit,
              "=", (total_sum := total_sum + digit ** 2))
        i = i + 1
        print("")
    print("\tSum of squared digits:", total_sum, "\n")
def main():
    inputs = [1, 5, 19, 25, 7]
    for i in range(len(inputs)):
        print(i+1, ".", "\tInput Number:", inputs[i], sep="")
        sum_of_squared_digits(inputs[i])

Enter to Rename, Shift+Enter to Preview

Happy Number

Next, we’ll initialise two variables fast and slow with the input number, and the sum of its digits respectively. In each iteration, we’ll move slow one step forward and fast two steps forward. That is, we’ll call the sum_of_squared_digits() function once for slow and twice for fast.

slow $=$ sum_of_squared_digits(slow)
fast $=$ sum_of_squared_digits(sum_of_squared_digits(fast))

If at any instance fast becomes $1$ , we’ve found a happy number. We’ll return TRUE in this case. Otherwise, if fast becomes equal to slow, we’ve found a loop and will return FALSE.

def is_happy_number(n):
    # Helper function that calculates the sum of squared digits.
    def sum_of_squared_digits(number):
        total_sum = 0
        while number > 0:
            number, digit = divmod(number, 10)
            total_sum += digit ** 2
        print("\t\tSum of squared digits: ", total_sum)
        return total_sum
    slow_pointer = n  # The slow pointer value
    print("\tSetting slow pointer = input number", slow_pointer)
    print("\tSetting fast pointer = sum of squared digits of ", n, sep="")
    fast_pointer = sum_of_squared_digits(n)  # The fast pointer value
    print("\tFast pointer:", fast_pointer)
    while fast_pointer != 1 and slow_pointer != fast_pointer:  # Terminating condition
        print("\n\tRepeatedly updating slow and fast pointers\n")
        # Incrementing the slow pointer by 1 iteration
        slow_pointer = sum_of_squared_digits(slow_pointer)
        print("\t\tThe updated slow pointer is", slow_pointer, "\n")
        # Incrementing the fast pointer by 2 iterations
        fast_pointer = sum_of_squared_digits(sum_of_squared_digits(fast_pointer))
        print("\t\tThe updated fast pointer is ", fast_pointer, "\n")
    # If 1 is found then it returns True, otherwise False
    if(fast_pointer == 1):
        print("\tSince fast pointer has converged to 1, the input number is a happy number.\n")
        return True
    print("\tFast pointer has not converged to 1, the input number is not happy number.\n")
    return False

Enter to Rename, Shift+Enter to Preview

Happy Number

def is_happy_number(n):
    # Helper function that calculates the sum of squared digits.
    def sum_of_squared_digits(number):
        total_sum = 0
        while number > 0:
            number, digit = divmod(number, 10)
            total_sum += digit ** 2
        return total_sum
    slow_pointer = n 
    fast_pointer = sum_of_squared_digits(n)  
    while fast_pointer != 1 and slow_pointer != fast_pointer: 
        slow_pointer = sum_of_squared_digits(slow_pointer)
        fast_pointer = sum_of_squared_digits(sum_of_squared_digits(fast_pointer))
    if(fast_pointer == 1):
        return True
    return False
def main():
    inputs = [1, 5, 19, 25, 7]
    for i in range(len(inputs)):
        print(i+1, ".\tInput Number: ", inputs[i], sep="")
        print("\n\tIs it a happy number? ", is_happy_number(inputs[i]))
        print("-" * 100)
if __name__ == '__main__':

Enter to Rename, Shift+Enter to Preview

Happy Number

Solution summary#

We maintain track of two values using a slow pointer and a fast pointer. The slow runner advances one number at each step, while the fast runner advances two numbers. We detect if there is any cycle by comparing the two values and checking if the fast runner has indeed reached the number one. We return True or False depending on if those conditions are met.

Time complexity#

The time complexity for this algorithm is $O(\log n)$ , where $n$ is the input number.

The worst case time complexity of this algorithm is given by the case of a non-happy number, since it gets stuck in a cycle, whereas a happy number quickly converges to $1$ . Let’s first calculate the time complexity of the Sum Digits function. Since we are calculating the sum of all digits in a number, the time complexity of this function is $O(\log n)$ , because the number of digits in the number $n$ is $\log_{10} n$ .

Before delving into the detailed complexity analysis, let's first consider the largest possible next number for each given number of digits:

To estimate the count of numbers in a cycle, let’s consider the following two cases:

Numbers with three digits: The largest three-digit number is $999$ . The sum of the squares of its digits is $243$ . Therefore, for three-digit numbers, no number in the cycle can go beyond $243$ . Therefore, the time complexity in this case is given as $O(243 \times 3)$ , where $243$ is the maximum count of numbers in a cycle and $3$ is the number of digits in a three-digit number. This is why the time complexity in the case of numbers with three digits comes out to be $O(1)$ .
Numbers with more than three digits: Any number with more than three digits will lose at least one digit at every step until it becomes a three-digit number. For example, the first four-digit number that we can get in the cycle is $1053$ , which is the sum of the square of the digits in $9999999999999$ . Therefore, the time complexity of any number with more than three digits can be expressed as $O(\log n + \log \log n + \log \log \log n + …)$ . Since $O(\log n)$ is the dominating term, we can write the time complexity as $O(\log n)$ .

Therefore, the total time complexity comes out to be $O(1 + \log n)$ , which is $O(\log n)$ .

Space complexity#

The space complexity for this algorithm is $O(1)$ .

Digits	Largest number	Sum of squared digits
1	9	81
2	99	162
3	999	243
4	9999	324
12	999999999999	972
13	9999999999999	1053
14	99999999999999	1134

Solution: Happy Number

Statement#

Solution#

Naive approach#

Optimized approach using Fast and Slow Pointers#

Step-by-step solution construction#

Just the code#

Solution summary#

Time complexity#

Space complexity#