To find the missing date, we will first initialize an array and call it Year with 70 spots (one for each year) where each spot contains the value 0.(70 space)
Next, we will then iterate through all the crosswords and we will only pay attention to the years. We look at each year of the crosswords and increment the corresponding value in the Year array. This takes \(n\) time.
We will then scan through the array and find the index that has the value \(364\) (instead of 365). This takes 70 time. Since that means that year is missing a single crossword.
Then, initialize an array with 12 spots (12 space) and call it Month.
Next, we will look through the crosswords again but we only look at the crosswords that come from the particular year that is missing a date. Then we will look at those months, and increment the position in the 12 spot array that corresponds to the correct month. This is a similar process to the above with the years array. \(n\) time.
We will then look through the 12 spot array, and find out which month is missing a day. (12 time)
Then we will create an array of 31 spots for the days. The space requirements is 31 in the worst case. For example, if the month is February, then you will only create a 28 spot array, or if it’s June, create a 30 spot array, etc.(31 space)
We will look at the crosswords again, but now, we only pay attention to the crosswords that come from the particular year and month that is missing a crossword. Like above, we increment the 31 spot array (n time).
Finally we look through the 31 spot array and find the date we are missing (31 time).
Analysis:
Total time: \(n + 70 + n + 12 + n + 31 = 3n = n\)
Total space: \(70+12+31=112\)