Puzzle

You are given an array with n elements { x1, x2 ... xk ... xn }. You are also given an array location k. Using constant space and O(n) time, rotate the array such that it contains { xk, xk+1 ... xn, x1, x2 ... xk-1 }.

Well the first thoughts which came to my mind were those involving swapping the elements and one can also achieve the solution this way, but its not the best way. The best way out is as follows:

We know that reversing of a list can be done in constant time. Thus do as follows:
1.reverse the list from x1 to xk-1 {xk-1, xk-2, ....., x1, xk, ...... , xn}
2.reverse the list from xk to xn {xk-1, xk-2, ....., x1, xn, ......., xk}
3.reverse the whole list {xk, xk+1, ..... xn, x1, x2, ......., xk-1}

Nice na!!!!