Non-Cyclical Number

Problem Statement

A non-cyclical number is an integer defined by the following algorithm:

• Given a positive integer, replace it with the sum of the squares of its digits.
• Repeat the above step until the number equals 1, or it loops infinitely in a cycle which does not include 1.
• If it stops at 1, then the number is a non-cyclical number.

Given a positive integer n, return true if it is a non-cyclical number, otherwise return false.

Example 1:

Input: n = 100

Output: True

Explanation: 1^2 + 0^2 + 0^2 = 1

Example 2:

Input: n = 101

Output: False

Explanation: 1^2 + 0^2 + 1^2 = 2 2^2 = 4 4^2 = 16 1^2 + 6^2 = 37 3^2 + 7^2 = 58 5^2 + 8^2 = 89 8^2 + 9^2 = 145 1^2 + 4^2 + 5^2 = 42 4^2 + 2^2 = 20 2^2 + 0^2 = 4 (This number has already been seen)

Constraints:

• 1 <= n <= 1000

Recommended Time and Space Complexity

You should aim for a solution with O(\log n) time complexity and O(\log n) or O(1) space complexity.

Solution

Hash Set

def is_happy(n: int) -> bool:
    """
    Determines if a number is a non-cyclical number using a hash set.

    Args:
        n: The input number.

    Returns:
        True if the number is a non-cyclical number, False otherwise.
    """
    seen = set()

    while n not in seen:
        seen.add(n)
        n = sum_of_squares(n)
        if n == 1:
            return True
    return False


def sum_of_squares(n: int) -> int:
    """
    Calculates the sum of squares of digits of a number.

    Args:
        n: The input number.

    Returns:
        The sum of the squares of the digits.
    """
    output = 0

    while n:
        digit = n % 10
        output += digit ** 2
        n //= 10
    return output

Time complexity: O(\log n) Space complexity: O(\log n)