Happy Number

EASY

Description

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

A happy number is a number defined by the following process:

Starting with any positive integer, replace the number by the sum of the squares of its digits.
Repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1.
Those numbers for which this process ends in 1 are happy.

Return true if n is a happy number, and false if not.

Example 1:

Input: n = 19
Output: true
Explanation:
1² + 9² = 82
8² + 2² = 68
6² + 8² = 100
1² + 0² + 0² = 1

Example 2:

Input: n = 2
Output: false

Constraints:

1 <= n <= 2³¹ - 1

Approaches

Checkout 2 different approaches to solve Happy Number. Click on different approaches to view the approach and algorithm in detail.

Brute Force with HashSet

Use a HashSet to track all numbers we've seen during the process. If we encounter a number we've already seen, we've detected a cycle and the number is not happy. If we reach 1, the number is happy.

Algorithm

Initialize an empty HashSet to store seen numbers
While the current number is not 1 and not in the HashSet:
- Add the current number to the HashSet
- Calculate the sum of squares of its digits
- Update the current number with this sum
If the current number is 1, return true
Otherwise, return false (cycle detected)

The approach works by repeatedly calculating the sum of squares of digits and storing each intermediate result in a HashSet. When we encounter a number that's already in our set, we know we're in a cycle and can return false. If we reach 1, we return true.

public boolean isHappy(int n) {
    Set<Integer> seen = new HashSet<>();
    
    while (n != 1 && !seen.contains(n)) {
        seen.add(n);
        n = getNext(n);
    }
    
    return n == 1;
}

private int getNext(int n) {
    int sum = 0;
    while (n > 0) {
        int digit = n % 10;
        sum += digit * digit;
        n /= 10;
    }
    return sum;
}

The getNext function extracts each digit by using modulo 10 operation, squares it, and adds to the sum. We then divide by 10 to move to the next digit.

Complexity Analysis

Time Complexity: O(log n) - The number of digits in n is O(log n), and we process each digit. The number of iterations before finding a cycle or reaching 1 is bounded.Space Complexity: O(log n) - In the worst case, we might store O(log n) numbers in the HashSet before detecting a cycle.

Pros and Cons

Pros:

Simple and intuitive implementation
Easy to understand and debug
Guaranteed to terminate

Cons:

Uses extra space to store all visited numbers
Not the most space-efficient solution

Code Solutions

Checking out 3 solutions in different languages for Happy Number. Click on different languages to view the code.

class Solution { public boolean isHappy ( int n ) { int slow = n , fast = next ( n ); while ( slow != fast ) { slow = next ( slow ); fast = next ( next ( fast )); } return slow == 1 ; } private int next ( int x ) { int y = 0 ; for (; x > 0 ; x /= 10 ) { y += ( x % 10 ) * ( x % 10 ); } return y ; } }

Video Solution

Watch the video walkthrough for Happy Number

Patterns:

MathTwo Pointers

Data Structures:

Hash Table

Companies:

Accenture |Airbnb |Cisco |Cognizant |