CareerCup

void RotateByK(int arr[], int length, int k)
 {
     Reverse(arr,0, k-1);
     Reverse(arr,k, length-1);
     Reverse(arr,0, length-1);
 }

 {1, 2, 3, 4, 5, 6, 7 }

 -> { 3, 2, 1 , 7, 6, 5, 4}
 -> { 4, 5, 6, 7 , 1, 2, 3}

I have written the following code....There can be an improvement in terms of performance, as this program shifts the array 1-position at a time for n-times..and thus shifting the array values n-positions...comments are appreciated....


#include <iostream>
#include <stdlib.h>
#include <time.h>

#define SIZE 5
using namespace std;


int RandomNum()
{
int random = 0;
srand ( time(NULL) );
random = rand() % (SIZE-1) + 1;
return random;
}

void moveBy(int* a,int n)
{
int temp = 0;
int index = 0;
for(int j = 0;j<n;j++)
{
int temp1 = a[0];
for(int i=0;i<SIZE-1;i++)
{
temp = a[i];
a[i] = a[i+1];
a[i+1] = temp;
}
for(int i=0;i<SIZE;i++)
{
cout<<"["<<i<<"]\t\t"<<a[i]<<endl;
}
}
}

int main()
{
int arr[SIZE];
int n = 0;

for(int i=0;i<SIZE;i++)
{
arr[i] = i;
}

n = RandomNum();
moveBy(arr,n);

return 0;
}

One Simple Approach with time Complexity O(N*K)

RotateByK(int Arr[]){
int i=0;
for(i=0; i<K; i++){
int key = Arr[n];
ShiftArray(Arr,0,n);
Arr[0]=key;
}
}

But this is not a optimal solution .. we can optimized this solution by just jumping k elements for example the last element will be replaced by Kth element directly and so on.
Modified approach will take O(N)

The code by Ramkumar is the best way to do it, using 3 string reverse and making it a O(n) affair. Each element in the array is accessed at least twice, because there are two reverse applied to each element. I was trying for a solution where each element will be accessed only once, hence making the factor 2 go away.

The idea,

Loop for K times:
{
1. Start with i=0
2. Any A[i] goes to A[(i+n) mod K]
3. j=(i+n) mod K
4. temp=A[j]
5. A[j]=A[i]
6. i=j
}

Note that if K (len) and n has some common factor, then this loop will rotate over the same elements again and again. This is avoided by using another variable turn which shifts the element to be properly placed next, when an element already placed is encountered.

The code:

void rotate(int A[],int len,int n)
{
	int turn=-1;		
// turn is used to ensure that our loop does not move over the same set of array 
// elements when len and n have a common factor
	int i=turn;
	int j,temp,temp2;
	for(int k=0;k<len;k++){
		if(i==turn){
			i++;			// first starts from A[0]
			turn++;
			temp=A[i];
		}
		j=(i+n)%len;
		temp2=A[j];
		A[j]=temp;
		temp=temp2;
		i=j;
	}
}

@manjesh.bits
though your sol is O(n*k) time but do you think wud it run as you think? code shouldn't never been put without checking else you can put psuedo code?

Start at i=0 and j=i+k and loop till j<length
Swap characters at input[i] and input[j]
i++, k++

This loop will happen n-k times.
So if we have 1,2,3,4,5,6,7,8,9,10,11 the above steps will return
7,8,9,10,11,6,1,2,3,4,5

Now set j=i+1 and do loop till j<n
swap input[i] and input[j]
i+, j++
On doing the above for 7,8,9,10,11,6,1,2,3,4,5 we get
7,8,9,10,11,1,2,3,4,5,6 which is the desired output. The second loop happens k times so when we add n-k+k we get O(n)
Code:

void swap(int* a, int* b)
{
int c = *a;
*a = *b;
*b = c;
}

void rotate(int a[], int n, int k)
{
if(k > n)
{
cout << "Cannot rotate" << endl;
return;
}
int i=0, j=i+k;
for(; j<n; i++,j++)
{
swap(&a[i], &a[j]);
}
j=i+1;
for(;j<n;i++,j++)
swap(&a[i],&a[j]);
}


int main(int argc, char** argv)
{
int a[11] = {1,2,3,4,5,6,7,8,9,10,11};
rotate(a, 11, 6);
for(int i=0; i<11; i++)
{
cout << a[i] << " ";
}
cout << endl;
}

Pasting formatted code

void swap(int* a, int* b)
{
  int c = *a; 
  *a = *b; 
  *b = c;
}

void rotate(int a[], int n, int k)
{
  if(k > n)
  {
  cout << "Cannot rotate" << endl;
  return;
  }
  int i=0, j=i+k;
  for(; j<n; i++,j++)
  {
   swap(&a[i], &a[j]);
  }
  j=i+1;
  for(;j<n;i++,j++)
       swap(&a[i],&a[j]);
}

int main(int argc, char** argv)
{
  int a[11] = {1,2,3,4,5,6,7,8,9,10,11};
  rotate(a, 11, 6);
  for(int i=0; i<11; i++)
  {
  cout << a[i] << " ";
  }
  cout << endl;
}

The above post was by me. Sorry, i'm new to careercup.

Any O(logn) solution ?

Hi,
Let's do it by an example. 1.2.3.4.5.6 shift by 2
1) Replace first 2 (n) elements with last (n) elements
5.6.3.4.1.2
2) Sort first array which has length = total array length - n (no. of element to move)
5.6.3.4
-> result will be 3.4.5.6
3) Now actual array will look like... 3.4.5.6.1.2

Complexity :- log (n-k) + in place exchange of n elements...

ramkumar's algorithm using string reverse is the best
but here is also another one if we could use additional place
here the number of swapping is less

1.to rotate by n places we create another array of size n with the first n numbers from the original array
2.then for the first element in this temporary array we push it to the currPos in original array +nth position example.for rotate by 2 the element at 0th position would go to 2nd position. the element at 2nd goes to 4th and so on until the possible position in the current array would surpass the array.
3.in that event we subtract the possible position with the total length and place that element in the array representing the difference. example if we are rotating by 3 then element at the 8th position in an array of size 10 would have possible position at 11 which is greater than 10 so we subtract and get 1, which is where the element would come on rotation.
4. we stop an iteration when we perform step 3 and restart step 2 for next element in the temp array we created in step 1.

example:
array: 1 2 3 4 5
rotate: 3

temp array : 1 2 3

for element 1 the position is 0+3 which is of element 4
the position of element 4 is 3+3 which is not less than 5 so the ultimate position is 3+3-5=1

array: 1 4 3 1 5

next element in temp array is 2 with possible position 1+3=4 which of element 5
element 5's possible position is 4+3>5 , therefore actual position is 7-5=2

array: 1 4 5 1 2

as we met with step 3 we switch to next element in temp array
next element is 3 with possible position 2+3= which is not less than 5, therefore the actual position is 5-5=0

array: 3 4 5 1 2

now since we surpassed the original array length we look at next element in the temp array, but no more element

so the final o/p: 3 4 5 1 2

Here one more approach (JAVA)
public void ringArray (int [] arr, int n){
int index = -1, newIndex= -1;
int len = arr.length;

System.out.println("I/P:");
for (int i = 0 ; i < len ; i++) {
System.out.print(arr[i]+"-");
}
for (int i =0 ; i< len ; i++ ) {
if (arr[i] == n) {
index = i;
newIndex = i+1;
break;
}
}
int roateFrq = len / newIndex;
if (len % newIndex == 0) {
roateFrq-=1;
}

System.out.println("\n"+roateFrq+"index:"+index);

for ( int k = 0 ; k < roateFrq && index < len ; k++ ) {
int backIndex = index;
int fwdIndex = index + newIndex;
if (! (fwdIndex < len)) {
fwdIndex = len-1;
}

for (int i = 0; i < newIndex; i++, backIndex --, fwdIndex-- ) {
System.out.println( arr[backIndex]+"->"+ arr[fwdIndex]);
int temp = arr[backIndex];
arr[backIndex] = arr[fwdIndex];
arr[fwdIndex] = temp;
}
index = index + newIndex;
System.out.println("index:"+index+ "newIndex:"+newIndex);
}
System.out.println("\nO/P:");
for (int i = 0 ; i < len ; i++) {
System.out.print(arr[i]+"-");
}
} // Method end ringArray

Pasting formatted code

public void ringArray (int [] arr, int n){
		int index = -1, newIndex= -1;
		int len = arr.length;
		
		System.out.println("I/P:");
		for (int i = 0 ; i < len ; i++) {
			System.out.print(arr[i]+"-"); 
		}
		for (int i =0 ; i< len ; i++ ) { 
			if (arr[i] == n) {
				index = i;
				newIndex = i+1;
				break;
			}
		}
		int roateFrq = len / newIndex;
		if (len % newIndex == 0) {
			roateFrq-=1;
		}
		
		System.out.println("\n"+roateFrq+"index:"+index);
		
		for ( int k = 0 ; k < roateFrq && index < len ; k++ ) {
			int backIndex = index;
			int fwdIndex = index + newIndex;
			if (! (fwdIndex < len)) {
				fwdIndex = len-1;
			}

			for (int i = 0; i < newIndex; i++, backIndex --, fwdIndex--  ) {
				System.out.println( arr[backIndex]+"->"+ arr[fwdIndex]);
				int temp = arr[backIndex];
				arr[backIndex] = arr[fwdIndex];
				arr[fwdIndex] = temp;
			}
			index = index + newIndex;
			System.out.println("index:"+index+ "newIndex:"+newIndex);
		}
		System.out.println("\nO/P:");
		for (int i = 0 ; i < len ; i++) {
			System.out.print(arr[i]+"-"); 
		}
	} // Method end ringArray

I think the question has been already answered in much better way. But I couldn't think of that approach by myself. Here's another approach:

Consider an array of 8 elements, to be rotated by 3, the indices are given below:
After: {5, 6, 7, 0, 1, 2, 3, 4}
Before: {0, 1, 2, 3, 4, 5, 6, 7}

We have one cycle, which covers all elements:

0 -> 3
3 -> 6
6 -> 1
1 -> 4
4 -> 7
7 -> 2
2 -> 5
5 -> 0

Now, consider another array, this time of 10 elements, to be rotated by 6, indices are given below:
After: {4, 5, 6, 7, 8, 9, 0, 1, 2, 3}
Before: {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}

We have two cycles:

Cycle1:
0 -> 6
6 -> 2
2 -> 8
8 -> 4
4 -> 0

Cycle2:
1 -> 7
7 -> 3
3 -> 9
9 -> 5
5 -> 1

Its not difficult to see that the number of cycles is gcd(n, k), where n is the array size and k is the rotation.
Proof: let g = gcd(n, k)
We have: i -> i+k -> i+2k -> ... i+(r-1)k -> i, therefore, i = i+rk, and (r*k)%n=0
we can write k as k=g*p, since r is the least number such that (r*g*p)%n=0, and p is coprime with n, we have n = g*r
r is the size of cycle and g is the number of cycles.


Withing each cycle, we only need to maintain one additional variable to achieve rotation.
Below is the algorithm:
g = gcd(n,k)
r = n/g
for(i=0; i<g; i++) {
temp = A[(i+(r-1)k)%n]
for(j=i+k; j<i+rk; j+=k)
A[j%n] = A[(j-k)%n];
A[i] = temp;
}

Here's the program:

#include <stdio.h>

int gcd(int p, int q) {
    if(p%q==0)
        return q;
    return gcd(q, p%q);
}

// rotate an array by k
void rotateArr(int A[], int n, int k) {
    int g, r, i, j, temp;
    g = gcd(n, k);
    r = n / g;
    
    for(i=0; i<g; i++) {
        temp = A[(i+(r-1)*k)%n];
        for(j=i+(r-1)*k; j>=i; j-=k)
            A[j%n] = A[(j-k)%n];
        A[i] = temp;
    }
}

void printArr(int A[], int n) {
    int i;
    for(i=0; i<n; i++)
        printf("%2d   ", A[i]);
    printf("\n");
}

int main() {
    int A[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    rotateArr(A, 10, 6);
    printArr(A, 10);
    
    return 0;
}

Output: 5 6 7 8 9 10 1 2 3 4

Isn't this solution is O(n) with space complexity of O(n)

import java.io.*;
class r
{
public static void main(String a[])
{
int ar[]={1,2,3,4,5,6,7};
int rot[]=new int[ar.length];
//rotation factor
int r=4;
for(int i=0;i<ar.length;++i,++r)
rot[r%rot.length]=ar[i];

//rotated array
for(int i:rot)
System.out.println(i);
}
}

Correct me if I am wrong..