Author: Rupanjan Hari
Tester: Rupanjan Hari
Basically, what you have to do is if you are given the number of terms in a series, you have to generate the skeleton series first i.e. if N=3 generate 0 1 2
Then, go for 0 1 2 -> 2 1 0 -> 2 0 1 -> 2 0 1
What has been shown over here is
- Reverse the series from term t1 to tn
- Reverse the updated series from t2 to tn
- Continue this process until you reach tn as the starting term.
This way a series of numbers will be generated where you have to search for the index of a specific number (i.e. K in the given problem) to provide as the output.
This is hell of an optimization problem where at first it might look easy but when the input number touches 10^3 limit , the game changes. Each output takes more than 6 seconds to generate and this time can even shoot up to 15 seconds for each output. So, I have to find a different way to find the solution to the problem. The solution was to generate the series at one shot else than reversing it for (N-1) times thus decreasing the complexity to O(n) form O(n^3).
If you look at the final series clearly, you can notice that t0 is equal to (N-1), the term followed is equal to (N-1) - t0 and the term followed is equal to (N-2) - t1 and this process follows for alternate index places i.e. if Loop Variable is even t(n)=(N-2) - t(n-1) otherwise t(n)=(N-1) - t(n-1).
Then linearly search the series for the index of the K number.
To make the problem look easy, I have divided the program into functions of appropriate name.
Arrays:N - This array stores the number of terms for each series K - This array stores the number you have to find the index of
Functions:void reverseBound(long a,long n) - This function generates the final series at one shot. void searchField(long a,long n,long s) - This array searches the **K** field.
click here to see the solution