The Middle Squares
InterviewTime limit1sMemory limit1024 MB
Repeatedly square the middle two digits of a four-digit number and count the steps until a value repeats.
- Level
Easy3 of 10
- Topics
- Simulation, Hash map
- Solved
- No attempts yet
Problem
Bessie's daughter, Cassie, came home from calf school with a new math problem. "I'm not sure I can do all the arithmetic," she whined.
"What is it you're doing?" asked her concerned mother.
"We are given a positive integer N less than 10,000," Cassie replied. "We treat it as a four digit number, even if it is something like 12. We extract the second and third digits to create a new number, then square it to create another four digit number. We repeat that until we reach a number we have already seen."
Help poor Cassie with her homework. Here is an example that starts with the number 4444:
N 2nd&3rd Squared
4444 ... 0044 ... 1936
1936 ... 0093 ... 8649
8649 ... 0064 ... 4096
4096 ... 0009 ... 0081
0081 ... 0008 ... 0064
0064 ... 0006 ... 0036
0036 ... 0003 ... 0009
0009 ... 0000 ... 0000
0000 ... 0000 ... 0000
This example requires nine iterations to complete. The number 0000 results in a loop, since its middle square is also 0000.
Input
The first line contains a single integer N.
Output
Print a single integer, the number of iterations before some number is duplicated.