Reverse Game HackerRank Ruby Solution Problem Statement
  
  Akash and Akhil are playing a game. They have N balls numbered from 0
  to N−1.         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.
  
  Input
  
  The 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\$.
  
  Output
  
  Print the final index in array.
  
  Constraints
  
  
  \$1 ≤ T ≤ 50\$
  \$1 ≤ N ≤ 10^5\$
  \$0≤K&lt;N\$
  
  
  Sample Input

2
3 1
5 2

  
  Sample Output

2
4

  
  Explanation
  
  
    For 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.
  


Solution

test = gets.chomp.to_i
test.times do
   num, numbered = gets.split.map(&amp;:to_i)
   a = []
   elem = 0 
   a &lt;&lt; elem

  (num-1).times do
   elem += 1
   a &lt;&lt; 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 &lt;&lt; elem
  w = q - [elem]
 end

 puts final.index(numbered)
end


My Problem

I 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?
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, 9


We then reverse the elements of the array starting at element 0:

9, 8, 7, 6, 5, 4, 3, 2, 1, 0


Then, we reverse all elements except the 0th element:

9, 0, 1, 2, 3, 4, 5, 6, 7, 8


Then we reverse all elements except 0th and 1st element:

9, 0, 8, 7, 6, 5, 4, 3, 2, 1


And so on like so:

9, 0, 8, 1, 2, 3, 4, 5, 6, 7
9, 0, 8, 1, 7, 6, 5, 4, 3, 2
9, 0, 8, 1, 7, 2, 3, 4, 5, 6
9, 0, 8, 1, 7, 2, 6, 5, 4, 3
9, 0, 8, 1, 7, 2, 6, 3, 4, 5


To get the final result:

9, 0, 8, 1, 7, 2, 6, 3, 5, 4


The key thing to note here is that if take every odd-indexed element we get:

9, 8, 7, 6, 5


While every even-indexed element is:

0, 1, 2, 3, 4


So it looks like the final sequence is constructed like this:


Split elements into lower half and upper half
Reverse the order of the upper half
Merge them by taking 1 element from upper half and 1 element from lower half and so on


This is an \$O(n)\$ process with the right implementation

All 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 array
If 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 pair


Note: this code ran in .05 sec for each trial under Python3.



Implementations are left as an exercise to the reader.