What is the best way to solve Happy Number?

The optimized O(n) approach using Math & Geometry patterns is generally preferred.

상위 150개 인터뷰쉬움

해피넘버

'행복한 숫자' 문제에 대한 자세한 가이드 및 Python 구현입니다.

문제 설명

쉬움

숫자 n이 만족스러운지 확인하는 알고리즘을 작성하세요.

행복한 숫자는 다음 프로세스에 의해 정의된 숫자입니다.

- 양의 정수로 시작하여 해당 숫자의 제곱의 합으로 숫자를 바꿉니다.

- 숫자가 1이 될 때까지(그대로 유지됨) 프로세스를 반복하거나 1을 포함하지 않는 주기로 끝없이 반복됩니다.

- 이 과정이 1로 끝나는 숫자는 행복합니다.

n이 행복한 숫자이면 true를 반환하고, 그렇지 않으면 false를 반환합니다.

isHappy(n: int) -> bool 함수를 구현하세요.

제약

•1 <= n <= 2^31 - 1

예

Example 1

Input

Output

True

Explanation

1^2 + 9^2 = 82. 8^2 + 2^2 = 68. 6^2 + 8^2 = 100. 1^2 + 0^2 + 0^2 = 1. Since we reached 1, 19 is a happy number.

Example 2

Input

Output

False

Explanation

2 -> 4 -> 16 -> 37 -> 58 -> 89 -> 145 -> 42 -> 20 -> 4 -> ... This loops forever without reaching 1.

Need a Hint?

세트나 힙과 같은 수학 및 기하학 관련 데이터 구조를 사용해 보세요.

Edge Cases to Watch

빈 입력 구조
단일 요소 입력
큰 수치 범위

해결할 준비가 되셨나요?

Open the problem in PyRun's browser-based Python editor. Your code runs fully offline — no server required.

편집기에서 열기

인터뷰 통찰력 및 변형

수학과 기하학 접근 방식의 논리를 설명하세요.

null 또는 빈 입력과 같은 극단적인 경우에 대해 논의합니다.

복잡성 분석 분석

무차별 대입 복잡성

Time: O(n)•Space: O(1)

왜 시간인가?: Directly evaluates all possibilities.

왜 우주인가?: Uses standard local memory.

최적화된 복잡성

Time: O(n)•Space: O(1)

왜 시간인가?: Optimized paths reduce total operations.

왜 우주인가?: May trade memory for speed.

최적화된 솔루션 Python 코드

컴파일러에서 시도해 보세요

def is_happy_opt(n: int) -> bool:
    def get_next(num):
        total = 0
        while num > 0:
            num, digit = divmod(num, 10)
            total += digit ** 2
        return total
    slow = n
    fast = get_next(n)
    while fast != 1 and slow != fast:
        slow = get_next(slow)
        fast = get_next(get_next(fast))
    return fast == 1

무차별 대입 코드(스포일러 보호)

컴파일러에서 시도해 보세요

def is_happy_brute(n: int) -> bool:
    def get_next(num):
        return sum(int(i)**2 for i in str(num))
    seen = set()
    while n != 1 and n not in seen:
        seen.add(n)
        n = get_next(n)
    return n == 1