Friday, March 14, 2008

Rotate an array of integers.

Simple one but little tricky.
Implement a function something like RotateArray(int array[], int nLen, int rotateBy), that will rotate the array by the given ammount.
For ex array is 1,2,3,4,5,6,7,8 and RotateArray(array, 8, 3) (rotateBy is 3) so afterthe function call the arry sould look like: 6,7,8, 1,2,3,4,5
..

Ok here goes my solution( O(n) ):

void RotateArray(int arr[], int len, int rotateBy) {
int i = 0;
int j = 0;

rotateBy = rotateBy%len;
do {
for (i = 0;i < rotateBy; i++) {
EXCHANGE(arr[j+i], arr[len-rotateBy+i])
}
j += i;
} while(j < len-rotateBy);
}

1 comment:

Yash said...

This solution does not give correct result for the case
array is 1,2,3,4,5,6,7,8 and RotateArray(array, 8, 3)

It gives 6,7,8,1,2,3,5,4

Though I also have a solution but this also has same bug. Analysing...

My Solution:
void MyRotateArray(int a[], int n, int m)
{
// length - n
// rotateBy - m

int add = n - m;
int cnt;
if ( m < n / 2)
{
cnt = n - m;
}
else
{
cnt = m;
}

for (int i = 0; i < cnt; i++)
{
if (i + add >= n)
{
add = n - add;
}
Exchange(a[i], a[i + add]);
}
}