Happy Number solution and explanation
Google
Cisco
9 more videos on this problem
Happy Number - Leetcode 202 - PythonNeetCode · 10:59 · 125K views
Happy Number (LeetCode 202) | Full solution with with easy explanation | Study AlgorithmsNikhil Lohia · 12:20 · 58K views
Leetcode 202. Happy NumberFraz · 5:57 · 15K views
LEETCODE 202 (JAVASCRIPT) | HAPPY NUMBERAndy Gala · 12:54 · 3K views
LeetCode 202 - Happy Number | Java SolutionCode with Carter · 8:30 · 2K views
202. Happy Number 🔥| Leetcode | Level 2 | JAVAProCode · 9:05 · 581 views
202. Happy Number - LeetCode SolutionGame of Coders · 4:22 · 468 views
Leetcode 202: Happy Number (Python Coding Interview Prep)Minted Maker · 4:49 · 243 views
LeetCode 202 | Happy Number | C++ ExplainedCompile With Priya · 7:16 · 176 views
Happy Number - LeetCode 202 | JAVAE-Leet Coding · 7:37 · 156 views
The problem
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 = 1
Example 2:
Input: n = 2 Output: false
Constraints:
1 <= n <= 231 - 1
Approach overview
Problem Overview: Given an integer n, repeatedly replace the number with the sum of the squares of its digits. If the process eventually reaches 1, the number is called a happy number. If the sequence enters a loop that never reaches 1, the number is not happy.
Approach 1: Using HashSet to Detect Cycles (O(log n) time, O(log n) space)
This approach simulates the process directly while tracking previously seen numbers. For each step, iterate through the digits of the current number, compute the sum of their squares, and generate the next value in the sequence. Store each intermediate value in a HashSet. If the sequence reaches 1, the number is happy. If a value repeats, the sequence has entered a cycle and will never reach 1.
The key insight is that unhappy numbers always fall into a repeating loop. A constant-time hash lookup detects when the loop starts. Each iteration processes the digits of the number, which takes O(log n) time because the number of digits grows logarithmically with n. The extra memory stores the sequence of previously seen values.
This method is straightforward and easy to reason about. If you're comfortable with hash tables, it's usually the fastest way to implement the solution during an interview.
Approach 2: Floyd's Cycle-Finding Algorithm (O(log n) time, O(1) space)
This approach eliminates the extra memory by treating the sequence as a linked list and detecting cycles using two pointers. Compute the next number using the same digit-square operation. Maintain a slow pointer that moves one step at a time and a fast pointer that moves two steps at a time. If the number is happy, the sequence eventually reaches 1. If a cycle exists, the two pointers will meet at some point in the loop.
Floyd's algorithm works because any repeating sequence behaves like a cycle in a linked structure. The slow/fast pointer technique guarantees detection without storing previous values. Each step still requires computing digit squares, so the time complexity remains O(log n), but the space complexity drops to O(1).
This solution combines ideas from two pointers and math problems. It is slightly trickier to implement but demonstrates strong understanding of cycle detection patterns.
Recommended for interviews: Start with the HashSet approach to show clear reasoning about cycle detection. Once that works, mention Floyd's cycle-finding optimization to reduce space to O(1). Interviewers typically expect candidates to recognize the cycle and either detect it with a set or optimize it using two pointers.
Approach 1: Approach 1: Using HashSet to Detect Cycles
The idea is to use a HashSet to track all numbers we've seen so far. If we encounter a number that we've seen before, it means we're in a cycle and the number is not happy. We keep replacing the number with the sum of the squares of its digits until we either reach 1 or the number starts repeating.
def isHappy(n):
def get_next(number):
return sum(int(char) ** 2 for char in str(number))
seen = set()
while n != 1 and n not in seen:
seen.add(n)
n = get_next(n)
return n == 1import java.util.HashSet;
class Solution {
public boolean isHappy(int n) {
HashSet<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 totalSum = 0;
while (n > 0) {
int d = n % 10;
n /= 10;
totalSum += d * d;
}
return totalSum;
}
}#include <unordered_set>
bool isHappy(int n) {
auto getNext = [](int n) {
int totalSum = 0;
while (n > 0) {
int d = n % 10;
n /= 10;
totalSum += d * d;
}
return totalSum;
};
std::unordered_set<int> seen;
while (n != 1 && seen.find(n) == seen.end()) {
seen.insert(n);
n = getNext(n);
}
return n == 1;
}function isHappy(n) {
const getNext = (num) => {
return num.toString().split('').reduce((sum, digit) => sum + Math.pow(parseInt(digit), 2), 0);
};
const seen = new Set();
while (n !== 1 && !seen.has(n)) {
seen.add(n);
n = getNext(n);
}
return n === 1;
}bool isHappy(int n) {
int getNext(int n) {
int totalSum = 0;
while (n > 0) {
int d = n % 10;
n = n / 10;
totalSum += d * d;
}
return totalSum;
}
int seen[1000] = {0};
while (n != 1 && !seen[n]) {
seen[n] = 1;
n = getNext(n);
}
return n == 1;
}using System.Collections.Generic;
public class Solution {
public bool IsHappy(int n) {
HashSet<int> seen = new HashSet<int>();
while (n != 1 && !seen.Contains(n)) {
seen.Add(n);
n = GetNext(n);
}
return n == 1;
}
private int GetNext(int n) {
int totalSum = 0;
while (n > 0) {
int d = n % 10;
n /= 10;
totalSum += d * d;
}
return totalSum;
}
}In this solution, we use a Python set to track all numbers observed so far. If the number is already in the set, it means a cycle is detected. The helper function get_next computes the sum of the squares of the digits.
Time Complexity: O(log n). Space Complexity: O(log n), since we store seen numbers.
Approach 2: Approach 2: Floyd's Cycle-Finding Algorithm
This approach utilizes Floyd's Cycle-Finding Algorithm (also known as Tortoise and Hare). Instead of using a hash set, we can use two pointers: a slow pointer and a fast pointer. The slow pointer moves one step at a time, whereas the fast pointer moves two steps at a time. If they meet, it means the sequence is cyclic.
def isHappy(n):
def get_next(number):
return sum(int(char) ** 2 for char in str(number))
slow, fast = n, get_next(n)
while fast != 1 and slow != fast:
slow = get_next(slow)
fast = get_next(get_next(fast))
return fast == 1class Solution {
public boolean isHappy(int n) {
int slow = n, fast = getNext(n);
while (fast != 1 && slow != fast) {
slow = getNext(slow);
fast = getNext(getNext(fast));
}
return fast == 1;
}
private int getNext(int n) {
int totalSum = 0;
while (n > 0) {
int d = n % 10;
n /= 10;
totalSum += d * d;
}
return totalSum;
}
}#include <iostream>
int getNext(int n) {
int totalSum = 0;
while (n > 0) {
int d = n % 10;
n /= 10;
totalSum += d * d;
}
return totalSum;
}
bool isHappy(int n) {
int slow = n, fast = getNext(n);
while (fast != 1 && slow != fast) {
slow = getNext(slow);
fast = getNext(getNext(fast));
}
return fast == 1;
}function isHappy(n) {
const getNext = (num) => {
return num.toString().split('').reduce((sum, digit) => sum + Math.pow(parseInt(digit), 2), 0);
};
let slow = n, fast = getNext(n);
while (fast !== 1 && slow !== fast) {
slow = getNext(slow);
fast = getNext(getNext(fast));
}
return fast === 1;
}int getNext(int n) {
int totalSum = 0;
while (n > 0) {
int d = n % 10;
n /= 10;
totalSum += d * d;
}
return totalSum;
}
int isHappy(int n) {
int slow = n;
int fast = getNext(n);
while (fast != 1 && slow != fast) {
slow = getNext(slow);
fast = getNext(getNext(fast));
}
return fast == 1;
}public class Solution {
public bool IsHappy(int n) {
int slow = n, fast = GetNext(n);
while (fast != 1 && slow != fast) {
slow = GetNext(slow);
fast = GetNext(GetNext(fast));
}
return fast == 1;
}
private int GetNext(int n) {
int totalSum = 0;
while (n > 0) {
int d = n % 10;
n /= 10;
totalSum += d * d;
}
return totalSum;
}
}Python implementation uses two pointers to identify cycles. Slow is incremented one step at a time; fast takes two steps. A collision without achieving 1 confirms a cycle.
Time Complexity: O(log n). Space Complexity: O(1), only using existing variables.
Approach 3: Default Approach
function isHappy(n: number): boolean {
const getNext = (n: number) => {
let res = 0;
while (n !== 0) {
res += (n % 10) ** 2;
n = Math.floor(n / 10);
}
return res;
};
const set = new Set();
while (n !== 1) {
const next = getNext(n);
if (set.has(next)) {
return false;
}
set.add(next);
n = next;
}
return true;
}func isHappy(n int) bool {
vis := map[int]bool{}
for n != 1 && !vis[n] {
vis[n] = true
x := 0
for ; n > 0; n /= 10 {
x += (n % 10) * (n % 10)
}
n = x
}
return n == 1
}use std::collections::HashSet;
impl Solution {
fn get_next(mut n: i32) -> i32 {
let mut res = 0;
while n != 0 {
res += (n % 10).pow(2);
n /= 10;
}
res
}
pub fn is_happy(mut n: i32) -> bool {
let mut set = HashSet::new();
while n != 1 {
let next = Self::get_next(n);
if set.contains(&next) {
return false;
}
set.insert(next);
n = next;
}
true
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Using HashSet to Detect Cycles | Time Complexity: O(log n). Space Complexity: O(log n), since we store seen numbers. |
| Approach 2: Floyd's Cycle-Finding Algorithm | Time Complexity: O(log n). Space Complexity: O(1), only using existing variables. |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| HashSet Cycle Detection | O(log n) | O(log n) | Best for clarity and quick implementation. Easy way to detect repeating states. |
| Floyd's Cycle-Finding Algorithm | O(log n) | O(1) | Use when memory must be minimized or when demonstrating cycle detection skills. |
Frequently asked questions
Is Happy Number easy or hard?
Happy Number is classified as an Easy problem. The main challenge is recognizing that the process forms a cycle and applying either a HashSet or Floyd's cycle detection to stop infinite loops.
Happy Number Python/Java solution
In Python or Java, repeatedly compute the sum of the squares of digits and track visited values using a set. Continue until the number becomes 1 or a previously seen value appears. Both implementations run in O(log n) time with simple loops and digit extraction.
How to solve Happy Number in O(1) space?
Use Floyd's cycle-finding algorithm with slow and fast pointers. The slow pointer applies the digit-square transformation once per step, while the fast pointer applies it twice. If the pointers meet at a number other than 1, the sequence forms a cycle and the number is not happy. This method runs in O(log n) time and O(1) space.
What is the best approach for Happy Number?
The most common approach uses a HashSet to detect cycles while repeatedly computing the sum of the squares of digits. If the sequence reaches 1, the number is happy. If a value repeats, a cycle exists and the number is not happy. This approach runs in O(log n) time per sequence step and uses O(log n) space.
Is Happy Number asked at Google/Amazon/Meta?
Happy Number is a common easy-level screening question and has appeared in interviews at companies like Amazon and Microsoft. It tests understanding of cycle detection, hashing, and number manipulation rather than complex algorithms.
What data structure is used in Happy Number?
The typical solution uses a HashSet to store previously seen numbers while generating the sequence. The set allows constant-time lookup to detect when the sequence repeats and enters a cycle.
What is the time complexity of Happy Number?
The time complexity is O(log n) because each iteration processes the digits of the number, and the number of digits grows logarithmically with n. The sequence length is small in practice since values quickly shrink into a bounded cycle. Space complexity is O(log n) with a HashSet or O(1) with Floyd's cycle detection.