Happy Number
Easy About 10 min Free, no account needed
Does repeatedly summing squared digits reach 1 - and how do you KNOW it will not?
The brief
Replace n by the sum of the squares of its digits, repeatedly. If the
process reaches 1, the number is happy. Unhappy numbers fall into a cycle
that never includes 1. Return whether n is happy.
A naive approach caps the iterations at an arbitrary count and hopes the
number would have reached 1 by then, which proves nothing and wastes work.
Unhappy numbers do not wander forever: they repeat. Detect that repetition
honestly instead of guessing at a cutoff. (Every chain provably falls below
1000 quickly, so whatever you track stays small.)
Starter code
using System;
public class Solution
{
// TODO: return true when iterating digit-square sums reaches 1.
public bool IsHappy(long n)
{
throw new NotImplementedException();
}
}How it is graded
Visible examples help you iterate. Hidden tests then cover edge cases and larger inputs, and every test reports server-measured time and allocated bytes.
What it practices
- Two pointers
- Walk a sorted or symmetric sequence from both ends, or fast and slow, instead of checking every pair.
- Math and number theory
- Replace enumeration with a formula: GCD, modular arithmetic, digit math and closed-form counting.
Related katas
- Add Binary Strings Easy Free Add two binary numbers far too long for any built-in integer.
- Base64 Decoded Length Easy Free The decoded size is pure arithmetic - no need to decode.
- Count Missing Sample Runs Easy Free Count every contiguous interval with no recorded sample, even when the timeline is too large to expand.
- Excel Column Number Easy Free Spreadsheet columns are base-26 with no zero digit.