InternDoor

Does the digit-square chain reach 1?

Easymath · cycle detection · hashing

Reported in interviews at (where)

Start from n and keep replacing the number with the sum of the squares of its digits. For example 23 becomes 2 * 2 + 3 * 3 = 13.

Return true if this reaches 1, and false if it goes round in a loop that never reaches 1.

Example 1
Input
n = 7
Output
true

7, 49, 97, 130, 10, 1.

Example 2
Input
n = 4
Output
false

4, 16, 37, 58, 89, 145, 42, 20 and then 4 again, so it loops without reaching 1.

Limits

  • 1 <= n <= 2147483647

Hints

Hint 1

The numbers soon become small, so if 1 never comes, some number must come round again.

Hint 2

Keep a set of the numbers seen, or run a slow and a fast copy of the chain until they meet.

Where this was reported

Our own problem on the task these candidates describe; the wording, examples and tests are InternDoor’s.

Run your code to check it on the examples. Submit runs every hidden test.

Ready for the real one?

Engineering internships and entry-level jobs in India, newest first.