When Jack was born, his parents listed down 1000 distinct times from 0 to 1000000, in hours since birth, and they also gathered 1000 timers.
When each specified hour on the list of times passed, Jack started a timer. Each timer starts at 0 and counts up 1 hour for every hour that passes. However, many of the timers are defective, and remain at 0 no matter how many hours pass.
For the purposes of this question, "current time" refers to the number of hours since Jack's birth. Jack wants to find the current time. Unfortunately, he forgot to associate each timer with a time. Given the initial list of 1000 times his parents created and the 1000 times on the timers, find the last three digits of the current time.
Sample input (with only 4 times)
2
3
5
9
0
1
0
4
Input explanation
The list of times is \([2,3,5,9]\). The list of timer times is \([0,1,0,4]\).
Answer and explanation
The current time is \(6\). The \(1\) must be associated with the \(5\), and the \(4\) with the \(2\). One timer showing \(0\) hasn't been started yet, and the other timer showing \(0\) is associated with \(3\), but is defective. Any other current time would not match up with the times on the timers.
Note that the actual input has 1000 times and 1000 timer times.
Details and assumptions
You may find the required numbers here. The first 1000 lines is the list of times, in numerical order, and the next 1000 lines are the times on the timers, in no particular order.
You may assume the current time is uniquely determined by the time on the timers.
by
Daniel Chiu
