Happy Number
EasyPrompt
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:
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1Example 2:
Input: n = 2
Output: false
Constraints:
1 <= n <= 231 - 1
Approaches
2 approaches with complexity analysis and trade-offs.
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)
Walkthrough
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
Time
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
O(log n) - In the worst case, we might store O(log n) numbers in the HashSet before detecting a cycle.
Trade-offs
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
Solutions
Solution
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 walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.