**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

__Output__: 4,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.

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

where 'n' is the number of elements 'k' is the interval by which array need to be rotated.

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

where k is the interval size.

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

__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,9k = 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:**nkwhere '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:**- Take an extra memory buffer which size is equal to 'k'
- Copy the elements from '0' to 'k-1' to the temporary memory buffer.
- Start moving the elements as 'k' to '0' , 'k + 1' to '1' and so on.
- Copy the temporary buffer data from 'n-k' position in the actual data array.

**Explanation:**Input -> 1,2,3,4,5,6,7,8,9k = 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:**kwhere k is the interval size.

__Approach 3__

Better Approach, without extra space

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

**Explanation:**Input -> 1,2,3,4,5,6,7,8,9k = 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
## No comments:

## Post a Comment