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

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(&: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)
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.

StackExchange Code Review Q#60271, answer score: 7