Happy numbers

You open a coding challenge from Apple and read: "Determine if a number is happy." The Happy Number problem (sometimes listed as Happy Number on other platforms) is a favorite among interviewers because it combines basic math operations with a critical computer science concept: cycle detection. It tests whether you can recognize when a process might loop forever and how to guard against it.

TL;DR

Repeatedly replace a number with the sum of the squares of its digits. If you reach 1, the number is happy. If you see the same number twice, you are in a cycle and the number is unhappy. Use a HashSet to track seen values. This runs in O(log n) time and O(n) space.

Why This Problem Matters

The happy number problem is a gateway to cycle detection, one of the most versatile patterns in technical interviews. The same idea of tracking visited states appears in linked list cycle detection, graph traversal, and even game theory problems. Recognizing when a process can loop and knowing how to detect that loop is a skill that transfers directly to harder problems.

Understanding the Problem

A happy number is a positive integer that eventually reaches 1 when you repeatedly replace it with the sum of the squares of its digits. If the process never reaches 1, the number is unhappy.

isHappy(19) -> true

This is because repeatedly applying the happy number algorithm to 19 yields 1:

1. 1^2 + 9^2 = 82
2. 8^2 + 2^2 = 68
3. 6^2 + 8^2 = 100
4. 1^2 + 0^2 + 0^2 = 1

Here is the full trace visualized:

Each step extracts every digit, squares it, and sums the results. After four iterations, 19 reaches 1, so it is happy.

Now consider 4, which is unhappy:

Starting from 4, the sequence passes through 16, 37, 58, 89, 145, 42, 20, and then back to 4. It is trapped in a cycle and will never reach 1.

The Key Insight

Unhappy numbers always enter a cycle. If you can detect that cycle, you can stop early and return false. This is where a HashSet comes in: store every number you have seen, and if you encounter one again, you know you are looping.

Solution Approach

The algorithm has two parts:

1. Digit square sum: A helper method that takes a number, extracts each digit using modulo and division, squares it, and accumulates the total.

2. Cycle detection with a HashSet: Keep processing until you either reach 1 (happy) or see a repeated value (unhappy).

Here is how the set tracks values for the unhappy case with n=4:

The moment we see 4 again, we know the number is unhappy and return false.

Implementation

Prefer a different language? Jump to solutions in other languages.

import java.util.HashSet;
import java.util.Set;

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

  private int step(int n) {
    int summed = 0;
    while (n > 0) {
      int units = n % 10;
      summed += units * units;
      n = n / 10;
    }
    return summed;
  }
}

Let's walk through the code:

1. Create a HashSet: This stores every intermediate value we compute so we can detect cycles.
2. Loop while n is not 1 and not seen: If n reaches 1, the number is happy. If n is already in the set, we have found a cycle.
3. Add n to the set, then compute the next value: The step method extracts each digit with n % 10, squares it, and adds it to a running sum. Then n / 10 removes the last digit.
4. Return whether n equals 1: After the loop, if n is 1, the number is happy. Otherwise, we exited because of a cycle.

Complexity Analysis

Time: O(log n). Each call to step processes every digit of the current number. A number with value n has O(log n) digits. The number of iterations before reaching 1 or entering a cycle is bounded by a constant for the constraint range (1 to 9999), because the maximum digit-square sum for a 4-digit number is 4 * 81 = 324, and all values in the range 1-324 either reach 1 or enter the known 8-element cycle within a fixed number of steps.

Space: O(n). In the worst case, every intermediate value is stored in the set. In practice, the set remains small because the cycle for unhappy numbers has only 8 elements, and happy numbers converge quickly.

Alternative: Floyd's Cycle Detection

You can avoid the HashSet entirely by using two pointers. A slow pointer advances one step at a time, while a fast pointer advances two steps. If they meet at 1, the number is happy. If they meet at any other value, there is a cycle.

public Boolean isHappy(int n) {
    int slow = n;
    int fast = step(n);
    while (fast != 1 && slow != fast) {
        slow = step(slow);
        fast = step(step(fast));
    }
    return fast == 1;
}

This runs in O(1) space but the same O(log n) time. For interviews, either approach is acceptable, but the HashSet version is more intuitive to explain.

Common Pitfalls

1. Infinite loop without cycle detection: If you simply loop until n equals 1 without checking for cycles, unhappy numbers will loop forever. Always guard against infinite iteration.

2. Integer overflow in digit extraction: For the given constraint (n up to 9999), overflow is not a concern. But if the constraint were larger, squaring digits and summing them could exceed integer bounds in some languages.

3. Forgetting integer division: Using floating-point division instead of integer division when removing the last digit (e.g., n / 10 in Java truncates, but n / 10 in Python 2 does not). Always use the language-appropriate integer division operator.

Interview Tips

When presenting this solution:

• Start by explaining what makes a number happy vs. unhappy. Draw a quick example on the whiteboard.
• Name the pattern: "This is a cycle detection problem." Interviewers appreciate when you identify the underlying technique.
• Walk through the step helper first. Show how n % 10 and n / 10 extract digits.
• Mention the Floyd's cycle detection alternative to show depth of knowledge, even if you implement the HashSet version.
• If asked about follow-ups, discuss how all unhappy numbers share the same 8-element cycle (4, 16, 37, 58, 89, 145, 42, 20).

Key Takeaways

• Happy numbers reach 1 through repeated digit-square sums. Unhappy numbers enter a cycle.
• A HashSet provides O(1) lookup to detect when you have revisited a value, making cycle detection straightforward.
• The digit extraction technique using n % 10 and n / 10 is a fundamental building block for many number-manipulation problems.
• Floyd's cycle detection offers an O(1) space alternative that uses the same principle as tortoise-and-hare in linked list problems.
• This problem connects math intuition with data structure choice. Recognizing that "repeated computation + possible loop = cycle detection" is a powerful interview skill.

Practice and Related Problems

Once you are comfortable with happy numbers, try these progressions:

• Linked list cycle detection (same cycle detection idea, different data structure)
• Find the duplicate number (Floyd's algorithm on an array)
• Digit root / digital root (similar digit manipulation without cycle detection)

This problem and hundreds of others are available on Firecode, where consistent daily practice helps you build the pattern recognition that top tech companies look for. Whether you are warming up for phone screens or preparing for on-site interviews, starting with fundamentals like this sets you up well.

Solutions in Other Languages

Python

class Solution:
    def is_happy(self, n: int) -> bool:
        seen = set()
        while n != 1 and n not in seen:
            seen.add(n)
            n = self.step(n)
        return n == 1

    def step(self, n: int) -> int:
        summed = 0
        while n > 0:
            units = n % 10
            summed += units * units
            n = n // 10
        return summed

JavaScript

class Solution {
  isHappy(n) {
    const seen = new Set();
    while (n !== 1 && !seen.has(n)) {
      seen.add(n);
      n = this.step(n);
    }
    return n === 1;
  }

  step(n) {
    let summed = 0;
    while (n > 0) {
      const units = n % 10;
      summed += units * units;
      n = Math.floor(n / 10);
    }
    return summed;
  }
}

module.exports = Solution;

TypeScript

class Solution {
  isHappy(n: number): boolean {
    const seen = new Set<number>();
    while (n !== 1 && !seen.has(n)) {
      seen.add(n);
      n = this.step(n);
    }
    return n === 1;
  }

  private step(n: number): number {
    let summed = 0;
    while (n > 0) {
      const units = n % 10;
      summed += units * units;
      n = Math.floor(n / 10);
    }
    return summed;
  }
}

export { Solution };

C++

#include <unordered_set>

class Solution {
public:
  bool isHappy(int n) {
    std::unordered_set<int> seen;
    while (n != 1 && seen.find(n) == seen.end()) {
      seen.insert(n);
      n = step(n);
    }
    return n == 1;
  }

private:
  int step(int n) {
    int summed = 0;
    while (n > 0) {
      int units = n % 10;
      summed += units * units;
      n = n / 10;
    }
    return summed;
  }
};

Go

package solution

func (s *Solution) IsHappy(n int) bool {
	seen := map[int]struct{}{}
	for n != 1 {
		if _, ok := seen[n]; ok {
			return false
		}
		seen[n] = struct{}{}
		n = step(n)
	}
	return n == 1
}

func step(n int) int {
	summed := 0
	for n > 0 {
		units := n % 10
		summed += units * units
		n = n / 10
	}
	return summed
}

type Solution struct {
}

Scala

import scala.collection.mutable

class Solution {
  def isHappy(n: Int): Boolean = {
    val seen = mutable.Set[Int]()
    var num = n
    while (num != 1 && !seen.contains(num)) {
      seen.add(num)
      num = step(num)
    }
    num == 1
  }

  private def step(n: Int): Int = {
    var summed: Int = 0
    var num = n
    while (num > 0) {
      val units = num % 10
      summed += units * units
      num = num / 10
    }
    summed
  }
}

Kotlin

class Solution {
    fun isHappy(n: Int): Boolean {
        val seen = mutableSetOf<Int>()
        var current = n
        while (current != 1 && !seen.contains(current)) {
            seen.add(current)
            current = step(current)
        }
        return current == 1
    }

    private fun step(n: Int): Int {
        var summed = 0
        var temp = n
        while (temp > 0) {
            val units = temp % 10
            summed += units * units
            temp = temp / 10
        }
        return summed
    }
}

Swift

import Foundation

class Solution {
    func isHappy(_ n: Int) -> Bool {
        var seen = Set<Int>()
        var current = n
        while current != 1 && !seen.contains(current) {
            seen.insert(current)
            current = step(current)
        }
        return current == 1
    }

    private func step(_ n: Int) -> Int {
        var summed = 0
        var num = n
        while num > 0 {
            let units = num % 10
            summed += units * units
            num = num / 10
        }
        return summed
    }
}

Rust

use std::collections::HashSet;

impl Solution {
    pub fn is_happy(&self, n: i32) -> bool {
        let mut seen: HashSet<i32> = HashSet::new();
        let mut n = n;
        while n != 1 && !seen.contains(&n) {
            seen.insert(n);
            n = self.step(n);
        }
        n == 1
    }

    fn step(&self, n: i32) -> i32 {
        let mut summed = 0;
        let mut n = n;
        while n > 0 {
            let units = n % 10;
            summed += units * units;
            n /= 10;
        }
        summed
    }
}

C#

using System.Collections.Generic;

public class Solution {
    public bool IsHappy(int n) {
        var seen = new HashSet<int>();
        while (n != 1 && !seen.Contains(n)) {
            seen.Add(n);
            n = Step(n);
        }
        return n == 1;
    }

    private int Step(int n) {
        var summed = 0;
        while (n > 0) {
            var units = n % 10;
            summed += units * units;
            n = n / 10;
        }
        return summed;
    }
}

Dart

class Solution {
  bool isHappy(int n) {
    Set<int> seen = {};
    while (n != 1 && !seen.contains(n)) {
      seen.add(n);
      n = _step(n);
    }
    return n == 1;
  }

  int _step(int n) {
    int summed = 0;
    while (n > 0) {
      int units = n % 10;
      summed += units * units;
      n = n ~/ 10;
    }
    return summed;
  }
}

PHP

class Solution {
    public function isHappy(int $n): bool {
        $seen = [];
        while ($n !== 1 && !isset($seen[$n])) {
            $seen[$n] = true;
            $n = $this->step($n);
        }
        return $n === 1;
    }

    private function step(int $n): int {
        $summed = 0;
        while ($n > 0) {
            $units = $n % 10;
            $summed += $units * $units;
            $n = intdiv($n, 10);
        }
        return $summed;
    }
}

Ruby

require 'set'

class Solution
  def is_happy(n)
    seen = Set.new
    while n != 1 && !seen.include?(n)
      seen.add(n)
      n = step(n)
    end
    n == 1
  end

  private def step(n)
    summed = 0
    while n > 0
      units = n % 10
      summed += units * units
      n = n / 10
    end
    summed
  end
end