Happy Number

To determine if a number is a happy number, we’ll repeatedly replace the number by the sum of the squares of its digits until we reach either 1 or a number we have seen before.

If we reach 1, the number is happy. If we find a number we have seen before, we are in a loop and the number is not happy.

Here’s the code implementing this logic:

1
2
3
4
5
6
7
8
9

class Solution:
    def isHappy(self, n: int) -> bool:
        seen = set()  # To keep track of numbers we have seen

        while n != 1 and n not in seen:
            seen.add(n)  # Add the current number to the seen set
            n = sum(int(i)**2 for i in str(n))  # Calculate the sum of the squares of the digits

        return n == 1  # Return True if the number is 1, otherwise False

Explanation:

  • We use a set seen to keep track of the numbers we have seen so far.
  • In the loop, we keep replacing n by the sum of the squares of its digits until n becomes 1 or we find a number we have seen before.
  • If n becomes 1, we return True; if we find a loop (a number in seen), we return False.

The time complexity of this solution depends on the number of steps it takes to reach either 1 or a loop. In practice, the time complexity is reasonable, and the space complexity is also bounded, as there are only a finite number of numbers that can be encountered before reaching a loop or 1.

Identifying Problem Isomorphism

“Happy Number” is approximately mapped to “Linked List Cycle II”.

Both problems revolve around detecting a cycle in a sequence of elements. In the “Happy Number” problem, the task is to find a cycle in the sequence of sums obtained from the squares of a number’s digits. In the “Linked List Cycle II” problem, the task is to identify a cycle within a linked list.

While the particular nature of the problem domains are different (one involving integer calculations and the other involving linked lists), the general strategy to solving these problems is very similar, as both involve cycle detection. This could be achieved using cycle detection algorithms like Floyd’s cycle-finding algorithm, often referred to as the “tortoise and hare” algorithm.

So, although the problems aren’t exactly the same, they share a common problem-solving approach, making them approximately isomorphic.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution:
    def isHappy(self, n: int) -> bool:
        slow = self.squared(n)
        fast = self.squared(self.squared(n))

        while slow!=fast and fast!=1:
            slow = self.squared(slow)
            fast = self.squared(self.squared(fast))

        return fast==1

    def squared(self, n):
        result = 0

        while n>0:
            last = n%10
            result += last * last
            n = n//10

        return result

Problem Classification

  1. Mathematical Problem: This problem involves performing mathematical operations like squaring and addition.

  2. Loop Detection: The problem involves detecting if a sequence of operations leads to a loop or cycle. This is a common problem in the field of graph theory and linked list data structures.

  3. Number Theory: Since the problem revolves around numbers and the properties derived from them (like being a “happy” number), it falls under this category.

Language Agnostic Coding Drills

To break down this problem, you can isolate the following concepts that can be learned and practiced separately:

  1. Loop: This code utilizes loops to continuously process data until a condition is met.

  2. Function Definition and Invocation: Two different functions (isHappy and squared) are defined and invoked in this code.

  3. Mathematical Operations: The code involves arithmetic operations such as modulo (%), floor division (//), and multiplication (*).

  4. Two Pointers Technique: The ‘slow’ and ‘fast’ pointers are used to detect the cycle in the transformations of the number n.

Here’s how to arrange the learning tasks in an increasing order of difficulty:

  1. Understanding and practicing mathematical operations in a programming language.

  2. Understanding and practicing how to define and invoke functions.

  3. Understanding and practicing loop controls, especially while-loops that continue until a certain condition is met.

  4. Learning and practicing the two pointers (slow and fast) technique, a common pattern in solving certain types of problems.

Here’s the step-by-step problem-solving approach for this problem:

  1. Understand the problem: The goal is to determine whether a given number is a “happy” number. A number is “happy” if you can eventually reach 1 by repeatedly replacing the number by the sum of the squares of its digits.

  2. Define the helper function squared: This function takes a number, separates its digits, squares each digit, and sums up all the squares.

  3. Define the main function isHappy: Use two pointers, ‘slow’ and ‘fast’, both starting from n. The ‘slow’ pointer applies the squared function once at each step, while the ‘fast’ pointer applies the squared function twice at each step. If a cycle is detected (i.e., slow == fast), exit the loop.

  4. Finally, return whether the ‘fast’ pointer reached 1, which indicates that the original number n is a “happy” number.

Targeted Drills in Python

  1. Mathematical Operations

For this, let’s practice a simple problem to find the sum of squares of digits in a number.

1
2
3
4
5
6
7
8
9

def sum_of_squares(n):
    total = 0
    while n > 0:
        digit = n % 10
        total += digit * digit
        n = n // 10
    return total

print(sum_of_squares(123))  # Output: 14
  1. Function Definition and Invocation

Here’s a drill to practice defining a simple function that checks if a number is odd or even, and then invoking it.

1
2
3
4
5

def is_odd(n):
    return n % 2 != 0

print(is_odd(5))  # Output: True
print(is_odd(4))  # Output: False
  1. Loop

This drill focuses on creating a loop that repeats until a condition is met. Let’s write a function that reduces a number to a single digit by continuously subtracting 2 until it’s not possible.

1
2
3
4
5
6

def reduce_to_single_digit(n):
    while n >= 10:
        n -= 2
    return n

print(reduce_to_single_digit(23))  # Output: 1
  1. Two Pointers Technique

The technique is often used in linked lists but for simplicity, we’ll apply it to an array. Let’s find if there’s a loop in an array, where each value is the index of the next position.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

def has_loop(arr):
    slow = fast = 0
    while True:
        if fast < len(arr) - 1:
            fast = arr[arr[fast]]
        else:
            return False
        if slow < len(arr):
            slow = arr[slow]
        else:
            return False
        if slow == fast:
            return True

print(has_loop([2, 0, 1, 3]))  # Output: True

Now, you can integrate these drills to solve the happy number problem.