Looping Number Fintech Python Interview Question

Given an integer , check if it is a looping number. A looping number has the following properties:

1. It is repeatedly replaced by the sum of the squares of its digits.
2. This process continues until:
   • The number becomes , in which case it is not a looping number.
   • The number starts repeating in a cycle that does not include , making it a looping number.

Return if is a looping number, otherwise return .

Example #1

Input:

Output:

Explanation:

1. $4^2 = 16$
2. $1^2 + 6^2 = 1 + 36 = 37$
3. $3^2 + 7^2 = 9 + 49 = 58$
4. $5^2 + 8^2 = 25 + 64 = 89$
5. $8^2 + 9^2 = 64 + 81 = 145$
6. $1^2 + 4^2 + 5^2 = 1 + 16 + 25 = 42$
7. $4^2 + 2^2 = 16 + 4 = 20$
8. $2^2 + 0^2 = 4 + 0 = 4$

Since the number loops back to , it is a looping number.

Example #2

Input:

Output:

Explanation:

1. $1^2 + 9^2 = 1 + 81 = 82$
2. $8^2 + 2^2 = 64 + 4 = 68$
3. $6^2 + 8^2 = 36 + 64 = 100$
4. $1^2 + 0^2 + 0^2 = 1 + 0 + 0 = 1$

Since the number reaches , it is not a looping number.

Loop Detection Using a Set

Intuition

The main idea of this approach is that if we reach a number (other than ) that we have seen before, it means the given number forms a loop.

For example, in the second example:

• We start from , and at step , the number changes back to .
• If we continue, we will only see the same numbers repeating, meaning a loop has formed.

On the other hand, if the number eventually becomes , then there is no loop.

Implementation

To check if a number appears more than once, we can use a set for quick lookup.

• Before adding a number to the set, we check if it already exists.
• If it does, we have detected a loop.
• Otherwise, we add the number to the set and continue.

Next, we need to compute the next number in the sequence. There are two ways to do this:

1. Using strings: Convert the number to a string, iterate over each character, convert it back to an integer, and sum the squares.
2. Using modulo: Extract the last digit using , square it, and remove it using integer division ().

Here’s the string-based approach:

Here’s the modulo-based approach (more efficient):

Here's the full implementation using the second (modulo-based) method to compute the next number:

Loop Detection Using the Tortoise and Hare Algorithm

The Tortoise and Hare Algorithm is a loop detection technique that uses two pointers moving at different speeds:

• The slow pointer (tortoise) moves one step at a time.
• The fast pointer (hare) moves two steps at a time.

If a loop exists, the two pointers will eventually meet at some point. Otherwise, if the fast pointer reaches , it means there is no loop, and we return .

In this problem:

• The slow pointer moves to the next computed number.
• The fast pointer moves to the next of the next computed number.
• If they become equal, there is a loop.
• If the fast pointer reaches , we return (indicating no loop).

If you're not familiar with the Tortoise and Hare Algorithm, you can read more here.

Here's the code: