First of all, there is no specific pattern for numbers so we need to calculate all of them. First of all we better calculate all the numbers and save them in an array. We need to do it extremely efficiently because 10^6 is large and we might easily end up getting TLE. So first of all the A[I] shows the answer for the number I. A[1] is 1 , then we need to continue, looping from 2 to 10^6 we need to calculate answer for every single answer, but we can be a little clever. Here is how, suppose we need to calculate for a specific number K. now we calculate all the numbers on the way, suppose we got Kn,Kn-1,.....1 so there are n numbers, So the answer for K is n. We calculated it successfully but there were numbers which we just threw away, the ones we got after K before reaching 1, isn't it true that the number after K has an answer of n-1 and the number after him has the answer of n-2.... So instead we can keep all the numbers we seen so far, and then when we reached 1 we can loop back and give each number on the way it's appropriate value which will save us a lot of time. Then the rest is just inputing and outputing the answer. NOTE on big note which caused me a lot of WA, it is not specified that in the input i is smaller or equal to j, this is important thing to consider. Also check out the source code for a better understanding,
No comments:
Post a Comment