Problem StatementAkash and Akhil are playing a game. They have N balls numbered from 0  to N1.         Akhil asks Akash to reverse the position of the balls,  i.e., to change the order from say, 0,1,2,3 to 3,2,1,0.   He further  asks Akash to reverse the position of the balls N times, each time  starting from one position further to the right, till he reaches the  last ball.    So, Akash has to reverse the positions of the ball  starting from 0th position, then from 1st position, then from 2nd  position and so on.At the end of the game, Akhil will ask Akash the final position of any  ball numbered K. Akash will win the game, if he can answer. Help  Akash.InputThe first line contains an integer \$T\$, i.e., the number of the test  cases. The next \$T\$ lines will contain two integers \$N\$ and \$K\$.OutputPrint the final index in array.Constraints\$1  T  50\$\$1  N  10^5\$\$0K<N\$Sample Input23 15 2Sample Output24ExplanationFor first test case, The rotation will be like this:    0 1 2 -> 2 1 0 -> 2 0 1 -> 2 0 1    So, Index of 1 will be 2.Solutiontest = gets.chomp.to_itest.times do   num, numbered = gets.split.map(&:to_i)   a = []   elem = 0    a << elem  (num-1).times do   elem += 1   a << elem  end  len = a.length  final = []  w = [] len.times do   if w.length == 0   q = a.reverse  else   q = w.reverse  end  elem = q.shift  final << elem  w = q - [elem] end puts final.index(numbered)endMy ProblemI could only pass 4 test cases out of 11 since it always timed out for the rest. This is happening because my solution isn't efficient enough.  How can we do it efficiently so that it passes all 11 test cases?
Reverse Game HackerRank Ruby Solution
optimization;algorithm;ruby;programming challenge;time limit exceeded
Let's analyze what the problem is saying.Let's say we start out with the array:0, 1, 2, 3, 4, 5, 6, 7, 8, 9We then reverse the elements of the array starting at element 0:9, 8, 7, 6, 5, 4, 3, 2, 1, 0Then, we reverse all elements except the 0th element:9, 0, 1, 2, 3, 4, 5, 6, 7, 8Then we reverse all elements except 0th and 1st element:9, 0, 8, 7, 6, 5, 4, 3, 2, 1And so on like so:9, 0, 8, 1, 2, 3, 4, 5, 6, 79, 0, 8, 1, 7, 6, 5, 4, 3, 29, 0, 8, 1, 7, 2, 3, 4, 5, 69, 0, 8, 1, 7, 2, 6, 5, 4, 39, 0, 8, 1, 7, 2, 6, 3, 4, 5To get the final result:9, 0, 8, 1, 7, 2, 6, 3, 5, 4The key thing to note here is that if take every odd-indexed element we get:9, 8, 7, 6, 5While every even-indexed element is:0, 1, 2, 3, 4So it looks like the final sequence is constructed like this:Split elements into lower half and upper halfReverse the order of the upper halfMerge them by taking 1 element from upper half and 1 element from lower half and so onThis is an \$O(n)\$ process with the right implementationAll that remains is to then search the list for the given element (which is \$O(n)\$ in the worst case with a standard implementation), yielding a final computational time complexity of \$O(n)\$. That's it, right? Well it would be, if not for some interesting math.If we apply some mathematical logic we can get an even faster solution:Decide if element is in lower half (which will have even indices) or the upper half (which will have odd indices) with a simple comparison to half the length of the arrayIf element is in lower half: final index will be 1 + 2 * K (as 0 will be in 1st index, 1 will be in 3rd, 2 will be in 5th and so on)If element is in upper half: final index will be 2 * (N - 1 - K) (as N - 1 will be at 0, N - 2 will be at 2, N - 3 will be at 4 and so on)This yields an \$O(1)\$ solution! Hurray for Math!You can also simplify the logic a bit by noticing an interesting fact:If you wrongly put an element from the upper half into the formula for the lower half and vice versa, an interesting thing happens: the final index will be out of the bounds of the array, and most importantly is greater than the index calculated from the other formula. The proof is left as an exercise, but this allows your entire program to boil down to:min(1 + 2 * K, 2 * (N - 1 - K)) for every N, K pairNote: this code ran in .05 sec for each trial under Python3.Implementations are left as an exercise to the reader.