CareerCup

What is the problem with this?

Say the array was [1, 2, 3, 4, 5, a, b , c]

With middle pointing at 'a'. First at 1, and last at 'c', and we need to rotate so that it is

[a, b, c, 1, 2, 3, 4, 5]

You make a copy of the First, Middle Iterators, say first', middle'.

Step 1)
Now start swapping using the first' and middle' (i.e. the copies) and incrementing, till either first' becomes middle or middle' becomes last.

Step 2)
Now (tail) recursively, rotate the rest.

In the above example, after Step 1 the resulting array looks like

[a, b, c, 4, 5, 1, 2, 3]

Now you need to rotate the sub-array [4, 5, 1, 2, 3] with middle at 1.

This is O(n) with O(1) space (assuming iterators take O(1) space, and besides, you need to store them anyway...)

#include <stdio.h>

void swap (char* ch1, char *ch2) {
     char ch = *ch1 ;
     *ch1 = *ch2 ;
     *ch2 = ch ;
}

void rotate (char *str, int first, int middle, int end) {
     int next = middle ;
     while ( first != next ) {
           swap ( &str[first++], &str[next++] ) ;
           if ( next == end ) 
              next = middle ;
           else if ( first == middle ) 
                middle = next ;
     }
}
       
int main () {
    char arr[] = {'1', '2', '3', '4', '5', 'a', 'b', 'c'} ;
    int i ;
    rotate (arr, 0, 5, 8) ;
    printf ( "\n" ) ;    
    for ( i = 0; i < 8; i ++ )
        printf ( "%c ", arr[i] ) ;
    printf ( "\n" ) ;
    return 0;
}

Simple implementation as written in std::rotate

Push every thing in stack. And pop and swap one by one. Another is recursive approach which uses internal stack. I doubt this can be solved without using extra memory. Recursion also uses stack.

A recursive function

void rotate(int a[], int n, int *left,int right)
{
  if(right==n)
    return ;
  rotate(a,n,left,right+1);
 swap(a[*left],a[right]);
 (*left)++;
 return;

}

Call this as
int left =0,right =0;

rotate(a,n,&left,right);

What does a forward-only iterator mean?

Can we move forward by more than 1 step?

If I assume that the array to be rotated is of size n and we have to rotate every element by r
Then r<n for a valid input
My approach is to start rotating from first element of the array continuously
Untill we complete one round
Then we replace the last element to be replaced with the first element of the array
Continue this cycle with second element of array and then third and so on upto r iterations
Afterwards we have a small sized problem of rotating only starting r elements with (r-n%r) steps

This should work, the time complexity is O(n) and space complexity is O(1)


public static void rotate(int [] array, int r) {
int n = array.length;
int gcd = utility.gcd(r, n);
int term = n/gcd;

int tmp;
int cur;
int nxt;
int store;
for (int i = 0; i < gcd; i++) {
cur = i;
store = array[cur];
for (int j = 0; j < term; j++) {
nxt = (cur + r)%n;
tmp = array[nxt];
array[nxt] = store;
store = tmp;
cur = nxt;

}
}
}


public static int gcd(int a, int b) {
int bigger = a > b?a:b;
int smaller = a > b?b:a;

while (smaller > 0) {
int tmp = bigger%smaller;
bigger = smaller;
smaller = tmp;
}
return bigger;
}

rotate(int *A, int k,int n)
{
reverse(A,0,n-k-1); ---->O(n) time, O(1) space
reverse(A,n-k,n-1); ---->O(n) time, O(1) space
reverse(A,0,n-1); ---->O(n) time, O(1) space
}

package org.wangbingold.datastructure.array;
/**
 * Question: 
Implement rotate function for forward-only iterators. 
Clarification: with O(1) additional memory. 
Rotate semantics should be that of std::rotate.
Example: 
Say the array was [1, 2, 3, 4, 5, a, b , c]. With middle pointing at 'a'. 
First at 1, and last at 'c', and we need to rotate so that it is [a, b, c, 1, 2, 3, 4, 5]. 
You make a copy of the First, Middle Iterators, say first', middle'.
*/

public class Rotation {
	
	private char[] array;
	
	public Rotation(char[] arrayIn){
		this.array = arrayIn;
	}
	
	/**
	 * Rotate the array in the range of [start, end] from the position of mid.
	 * */
	public void rotate(int start, int mid, int end){
		if(start>=end){
			return;
		}
		int numPart1 = mid-start;
		int numPart2 = end-mid+1;
		int p1 = start; 
		int p2 = mid; 
		if(numPart1==numPart2){
			while(p2<=end){
				char tmp = array[p1];
				array[p1] = array[p2];
				array[p2] = tmp;
				p1++;p2++;
			}
			System.out.println(this.toString());
		}
		else if(numPart1>numPart2){
			while(p2<=end){
				char tmp = array[p1];
				array[p1] = array[p2];
				array[p2] = tmp;
				p1++;p2++;
			}
			int newStart = p1;
			int newEnd = p2-1;
			int newMid = newStart+numPart1-numPart2;
			System.out.println(this.toString());
			rotate(newStart, newMid, newEnd);
		}
		else if(numPart1<numPart2){
			while(p1<mid){
				char tmp = array[p1];
				array[p1] = array[p2];
				array[p2] = tmp;
				p1++;p2++;
			}
			int newStart = p1;
			int newEnd = (p2==end)?p2:p2+1;
			int newMid = (p2>end)?p2-1:p2;
			System.out.println(this.toString());
			rotate(newStart, newMid, newEnd);
		}
	}
	
	public String toString(){
		String result="";
		for(Object obj: array){
			result+=obj.toString()+" ";
		}
		return result;
	}
	
	public static void main(String[] args){
		Rotation rotation = new Rotation(new char[]{'1','2','3','4','5','a','b','c'});
		rotation.rotate(0, 5, 7);
	}

}

Is this what you're looking for?

cplusplus.com/reference/algorithm/rotate/

package google;

public class rotate_string_with_1_additional_data_and_O_n {


public static String rotate(String aim,int index){
if(index<=0){
return aim;
}
if(index>=aim.length()){
return aim;
}
char[] test=aim.toCharArray();
do_work(test,0,index,test.length-1);
return String.valueOf(test);
}

public static void do_work(char[] test,int bIndex,int mIndex,int eIndex){

if(mIndex-bIndex==eIndex-mIndex+1){
deal_char_array(test,bIndex,eIndex,(eIndex-bIndex+1)/2);
return;
}
else if(mIndex-bIndex>eIndex-mIndex+1){
int size=eIndex-mIndex+1;
deal_char_array(test,bIndex,eIndex,size);
do_work(test,bIndex+size,mIndex,eIndex);
}
else{
int size=mIndex-bIndex;
deal_char_array(test,bIndex,eIndex,size);
do_work(test,bIndex,bIndex+size,eIndex-size);
}
}
public static void deal_char_array(char[] test,int begin,int end,int size){
if((size>(end-begin+1)/2)||(size<1)){
System.out.println("err");
return;
}
for(int i=0;i!=size;i++){
char tmp=test[begin+i];
test[begin+i]=test[end-size+1+i];
test[end-size+1+i]=tmp;
}
}

public static void main(String[] args) {
String aim="abcde123456";
String result=rotate(aim,5);
System.out.println(result);

}
}

void STD_Rotate(std::vector<int>::iterator& begin, std::vector<int>::iterator& rotate, std::vector<int>::iterator& end)
{
	if(rotate == end)
		return;

	int size = rotate - begin;
	int value;

	while( rotate != end )
	{
		value = *rotate;
		while(size > 0)
		{
			*(begin+size) = *(begin+size-1);
			--size;
		}
		size = rotate - begin;
		*(begin) = value;
		++begin;
		rotate = begin+size;
	}
}

Formally, for every integer n such that 0 <= n < last - first, the element *(first + n) is assigned to *(first + (n + (last - middle)) % (last - first)). Rotate returns first + (last - middle).

Simple solution :

public void rotateArrayLikeSTLRotate(int[] arr) throws Exception
	{
		if(arr != null && arr.length > 1)
		{
			int len = arr.length;
			int mid = (len-1)/2;
			int start = 0;
			int end = len - 1;

			for (int i = 0; i <= mid; i++)
			{
				//Swap i th element with end-mid+i th element
				int temp = arr[i];
				arr[i] = arr[end - mid + i];
				arr[end - mid + i] = temp;
			}

		}
		else
		{
			throw new Exception("Invalid input parameters");
		}
	}

Well... cplusplus.com has it all

cplusplus.com/reference/algorithm/rotate/

It is basically anonymous' solution converted to an iterative version

How about Jigsaw Algorithm for this. That is mentioned in Programming Pearl by John Bently.

#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>

using namespace std;
typedef vector<int>::iterator viter;

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

void myRotation(vector<int>& vec,
                viter middle) {
        viter first = vec.begin();
        viter last = vec.end();
        viter next = middle;

        while(first != next) {
                swap(*first++, *next++);
                if(next == last) next = middle;
                else if(first == middle) middle = next;
        }
}

int main() {
        int arr[] = {1,2,3,4,5,6,7};
        vector<int> vec(arr, arr+sizeof(arr)/sizeof(int));
        copy(vec.begin(), vec.end(), ostream_iterator<int>(cout, " "));
        cout << endl;
        myRotation(vec, vec.begin()+2);
        copy(vec.begin(), vec.end(), ostream_iterator<int>(cout, " "));
        cout << endl;

        return 0;
}

Suppose you want to rotate array by K so first reverse last K elements i.e array[n-K+1...K], then reverse array[1..n-k], then reverse entire array array[1...n] and you will get the result.

Example:
array=[1,2,3,4,5,a,b,c]
K=3, here
reverse array[n-K+1... n] so the array will become [1,2,3,4,5,c,b,a].
Now reverse array[1...n-K], array will become [5,4,3,2,1,c,b,a].
Now reverse entire array and array will become [a,b,c,1,2,3,4,5].

Time complexity: O(n), Space complexity: O(n)..