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
Use Floyd's cycle detection algorithm with slow and fast pointers. The slow pointer moves one step at a time, while the fast pointer moves two steps. If there's a cycle, they will eventually meet. If the fast pointer reaches 1, the number is happy.
Algorithm
- Initialize two pointers (slow and fast) to the input number
- Repeat until the pointers meet:
- Move slow pointer one step (calculate sum of squares once)
- Move fast pointer two steps (calculate sum of squares twice)
- When pointers meet, check if they met at 1
- Return true if they met at 1, false otherwise
Walkthrough
This approach treats the problem as cycle detection in a sequence. We use two pointers moving at different speeds - if there's a cycle, they will eventually meet at the same number. If the fast pointer reaches 1, we know the number is happy.
public boolean isHappy(int n) { int slow = n; int fast = n; do { slow = getNext(slow); fast = getNext(getNext(fast)); } while (slow != fast); return slow == 1;} private int getNext(int n) { int sum = 0; while (n > 0) { int digit = n % 10; sum += digit * digit; n /= 10; } return sum;}The algorithm works because:
- If there's a cycle, the fast pointer will eventually catch up to the slow pointer
- If the sequence reaches 1, it will stay at 1 (since 1² = 1)
- When the pointers meet, we check if they met at 1
Complexity
Time
O(log n) - Similar to the HashSet approach, we process digits and the number of iterations is bounded.
Space
O(1) - We only use two integer variables regardless of input size.
Trade-offs
Pros
Constant space complexity
No need to store visited numbers
Elegant solution using well-known algorithm
Cons
Slightly less intuitive than the HashSet approach
Requires understanding of Floyd's cycle detection algorithm
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 ; } }class Solution { public: bool isHappy ( int n ) { auto next = []( int x ) { int y = 0 ; for (; x ; x /= 10 ) { y += pow ( x % 10 , 2 ); } return y ; }; int slow = n , fast = next ( n ); while ( slow != fast ) { slow = next ( slow ); fast = next ( next ( fast )); } return slow == 1 ; } };class Solution : def isHappy ( self , n : int ) -> bool : def next ( x ): y = 0 while x : x , v = divmod ( x , 10 ) y += v * v return y slow , fast = n , next ( n ) while slow != fast : slow , fast = next ( slow ), next ( next ( fast )) return slow == 1Video 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.