Friday, September 13, 2013

Puzzle 6: Rotate the array with the given number of intervals.

Puzzle 6: Rotate the array with the given number of intervals.
Example: 
             Input: 1,2,3,4,5,6,7,8,9
                          Rotate it by 3 position
             Output4,5,6,7,8,9,1,2,3

Solution:
There can be number of approaches to do this, I will try to explain some any new approach will be really appreciable.


Approach 1
Brute force method
Method: Rotate each element by one position for k - times, where k is the interval by which array need to be rotated.
Example: Input -> 1,2,3,4,5,6,7,8,9
k = 3
Run a loop to rotate each element by one place
Iteration 1, Array becomes:                                       2,3,4,5,6,7,8,9,1
Iteration 2, Array becomes:                                       3,4,5,6,7,8,9,1,2
Iteration 3, Array becomes:                                       4,5,6,7,8,9,1,2,3
Complexity: nk
where 'n' is the number of elements 'k' is the interval by which array need to be rotated.
Space Complexity: 0



Approach 2
Using extra memory
Method: 

  1. Take an extra memory buffer which size is equal to 'k'
  2. Copy the elements from '0' to 'k-1' to the temporary memory buffer.
  3. Start moving the elements as 'k' to '0' , 'k + 1' to '1' and so on.
  4. Copy the temporary buffer data from 'n-k' position in the actual data array.

Explanation: Input -> 1,2,3,4,5,6,7,8,9
k = 3
Allocate a temporary buffer of size k = 3;
Copy data from the input array to temporary buffer upto 'k' position.
Array becomes:                               -, - , - ,4,5,6,7,8,9
Start moving the data by 'k' position, array becomes:
Array becomes:                               4,5,6,7,8,9, - , - , -
Copy the data from the temporary buffer to the actual data.
Array becomes:                               4,5,6,7,8,9,1,2,3
Complexity: n
Space Complexity: k
where k is the interval size.



Approach 3
Better Approach, without extra space
Method: 

  1. Divide the array in two subset of size 'k' and 'n-k'.
  2. Rotate each subset which will take n time.
  3. Rotate the whole data again and you will get the desired output.

Explanation: Input -> 1,2,3,4,5,6,7,8,9
k = 3

Divide the data in two subset as follows:
{1,2,3}  , {4,5,6,7,8,9}

Rotate each subset individually, the output will be
{3,2,1}  , {9,8,7,6,5,4}

Rotate the whole data data at once now.
4,5,6,7,8,9,1,2,3

Complexity: n
Space Complexity: 0