Does the digit-square sequence reach 1
Easy · Target 10 minutes · Two pointers· Type asked at
J.P. Morgan
DRW
Nvidia
You start with a positive integer n and keep replacing it with the sum of the squares of
its digits, and if you eventually get to 1 then n is called happy. You'd return true if it
is and false if the sequence ends up going round a loop that never has 1 in it.
Examples
| Input | Output | Why |
|---|---|---|
n = 19 | true | 19 → 82 → 68 → 100 → 1. |
n = 2 | false | 2 → 4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4, and you're back at 4 for good. |
n = 7 | true | 7 → 49 → 97 → 130 → 10 → 1. |
Constraints
- 1 ≤ n ≤ 2³¹ − 1
Hints
Hint 1
Do you think the sequence could just keep on growing? I'd look at what happens to a number with ten digits and ask how big the sum of the squares of its digits could possibly be.
Hint 2
It's at most 10 × 81 = 810, so after one step you're below 1,000 and you'll stay there. That means the sequence has to repeat, and either it gets to 1 (which maps to itself) or it goes round a loop.
Hint 3
You could keep every value you've seen in a set, or you can run a slow pointer one step at a time and a fast one two steps at a time and stop when they meet, and then check whether it was at 1 that they met.
Where people lose marks
- Looping until you see 1 with nothing else to stop you, which never ends on a number like 2.
- Checking only for 4 as the sign of an unhappy number. It happens to be true that every unhappy number reaches 4, but it's a fact you'd have to prove in the interview, and cycle detection doesn't need it.
- Overflow when n is close to 2³¹. The sum of the squares of ten digits is at most 810, so the step itself is safe, as long as you don't square the whole number by mistake.
Dry run on 2
Read it one frame at a time, the way you would trace the code on paper in an interview. Each frame shows the state after the step it describes.
-
Step 1 / 9sequence2041162373584895145642720849slow2fast4
The sequence from 2 starts 2 → 4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4. slow is at 2, and fast has taken one step to 4 ahead of it.
-
Step 2 / 9sequence2041162373584895145642720849slow4fast37
slow takes one step to 4 and fast takes two to 37.
-
Step 3 / 9sequence2041162373584895145642720849slow16fast89
Now slow's at 16 and fast has jumped on to 89.
-
Step 4 / 9sequence2041162373584895145642720849slow37fast42
slow takes one step to 37 and fast takes two to 42.
-
Step 5 / 9sequence2041162373584895145642720849slow58fast4
Now slow's at 58 and fast has jumped on to 4.
-
Step 6 / 9sequence2041162373584895145642720849slow89fast37
slow takes one step to 89 and fast takes two to 37.
-
Step 7 / 9sequence2041162373584895145642720849slow145fast89
Now slow's at 145 and fast has jumped on to 89.
-
Step 8 / 9sequence2041162373584895145642720849slow42fast42
slow takes one step to 42 and fast takes two to 42.
-
Step 9 / 9sequence2041162373584895145642720849resultfalse
They met at 42, which isn't 1, so the sequence is stuck in a loop and 2 isn't happy.
How to think about it
The first thing I'd want to know is that the sequence can't run off to infinity. A number with d digits is at least 10^(d−1), and the sum of the squares of its digits is at most 81d, which is smaller once d is 4 or more. Any value from 1,000 up gets smaller in one step, and anything below 1,000 maps to at most 81 × 3 = 243. So the sequence ends up trapped below 1,000 and has to repeat a value at some point.
Once you know it repeats, there are only two ways it can go. Either it reaches 1, and 1 maps to 1 so it sits there, or it goes round a loop that doesn't contain 1. A set of the values you've seen tells you which, but the set isn't needed. A slow pointer that takes one step and a fast one that takes two will meet once they're both in the final loop, and if that loop is 1 on its own they'll meet at 1. So I'd return whether they met at 1.
This is the same as Floyd's method on a linked list, where the next pointer is a function you work out as you go and not something stored in memory.
Complexity. Time O(log n) for the first step, then O(1) because everything is below 1,000 · Space O(1)
The solution, in six languages
Each one is compiled and run against the test table before it is published. Java is reviewed by hand.
def is_happy(n):
def step(x): # the next value in the sequence
s = 0
while x:
x, d = divmod(x, 10)
s += d * d
return s
slow, fast = n, step(n)
while fast != 1 and slow != fast: # fast hits 1 or the two meet in a loop
slow = step(slow)
fast = step(step(fast))
return fast == 1static long long step(long long x) { // the next value in the sequence
long long s = 0;
for (; x > 0; x /= 10) s += (x % 10) * (x % 10);
return s;
}
bool solve(long long n) {
long long slow = n, fast = step(n);
while (fast != 1 && slow != fast) { slow = step(slow); fast = step(step(fast)); }
return fast == 1;
}class Solution {
private long step(long x) { // the next value in the sequence
long s = 0;
for (; x > 0; x /= 10) s += (x % 10) * (x % 10);
return s;
}
public boolean isHappy(long n) {
long slow = n, fast = step(n);
while (fast != 1 && slow != fast) { slow = step(slow); fast = step(step(fast)); }
return fast == 1;
}
}function isHappy(n) {
const step = x => { // the next value in the sequence
let s = 0;
for (; x > 0; x = Math.floor(x / 10)) s += (x % 10) ** 2;
return s;
};
let slow = n, fast = step(n);
while (fast !== 1 && slow !== fast) { slow = step(slow); fast = step(step(fast)); }
return fast === 1;
}fn step(mut x: i64) -> i64 { // the next value in the sequence
let mut s = 0;
while x > 0 { s += (x % 10) * (x % 10); x /= 10; }
s
}
fn solve(n: i64) -> bool {
let (mut slow, mut fast) = (n, step(n));
while fast != 1 && slow != fast { slow = step(slow); fast = step(step(fast)); }
fast == 1
}solve :: Int -> Bool
solve n = go n (step n)
where
-- the next value in the sequence
step 0 = 0
step x = let (q, d) = x `divMod` 10 in d * d + step q
go slow fast
| fast == 1 = True
| slow == fast = False
| otherwise = go (step slow) (step (step fast))Variants to try
- If you're asked to count the happy numbers up to N, I'd use the fact that every value drops below 1,000 in one step and work out the answer for 1..999 once, so the rest is a lookup.
- If it's cubes instead of squares the same bound argument still works (with a bigger limit) and you won't have to change the cycle detection at all.
Next problems
The repeated number, without changing the array
Read the array as a list where index i points to nums[i]. The repeated value is where two arrows meet, which is the start of a cycle, and Floyd finds it in O(1) space.
Open the problem → Medium15 minWhere a linked list loops back on itself
A list starts at node 0 and might end or might loop. Floyd's two phases tell you which, and where the loop starts, in O(1) space.
Open the problem → Easy10 minMove the zeros to the end
One pointer reads every element, the other marks where the next non-zero belongs. The order of the non-zero values is kept.
Open the problem →Write a solution and run it against the real test table.
Keep going
The repeated number, without changing the array
Read the array as a list where index i points to nums[i]. The repeated value is where two arrows meet, which is the start of a cycle, and Floyd finds it in O(1) space.
Open the problem → Medium15 minWhere a linked list loops back on itself
A list starts at node 0 and might end or might loop. Floyd's two phases tell you which, and where the loop starts, in O(1) space.
Open the problem → Easy10 minMove the zeros to the end
One pointer reads every element, the other marks where the next non-zero belongs. The order of the non-zero values is kept.
Open the problem → Two pointersThe pattern behind it
Two indices walking a sorted or paired structure, each step ruling out one candidate for good.
Read the pattern →Preparing for a real process? Quant interview preparation, or book a free 20-minute call.