CareerCup

Binary Search could be used, compare the middle element A[m] with next element A[m+1], if A[m] > A[m+1], then m is the turning point; else compare A[m] with A[0] to determine the next range, code as follow:

#include <vector>

using namespace std;

class Solution {
public:
    int pos(vector<int> v) {
        int len = v.size();
        
        if(len < 2) {
            return 0;
        }
        
        int s = 0, e = len-1;
        
        while(s <= e) {
            int m = s + (e-s)/2;
            
            if(m < len && v[m] > v[m+1]) {
                return m;
            }
            else if(v[m] > v[0]) {
                s = m+1;
            }
            else {
                e = m-1;
            }
        }
        
        return 0;
    }
};

lets array length is L

reminder = n % L

reminder < (L-reminder) ? reminder : (L-reminder)

ex: 1 2 3 4 5 6 7 8 9
case 1: n = 13
reminder = 13%9 = 4

6 7 8 9 1 2 3 4 5 here 6 7 8 9 (4 numbers) are not in correct position

case 2: n = 23
reminder = 23%9 = 5

5 6 7 8 9 1 2 3 4 here 1 2 3 4 is not in correct position, here return reminder or (L-reminder) which ever is smaller

to print the numbers that are not in correct position

if(reminder < (L-reminder))
{
    for(int i=0; i < reminder; i++)
        cout << a[i] << " ";
}
else
{
    for(int i=reminder; i < L; i++)
        cout << a[i] << " ";
}

1 #include<iostream>
  2 #include<cstring>
  3 #include<algorithm>
  4 #include<iterator>
  5 
  6 void swap(int array[],const int& length,const int& swaps)
  7 {
  8     int temp_array[swaps];
  9     memmove(temp_array,array+(length-swaps),sizeof(int)*swaps);
 10     memmove(array+(length-swaps),array,sizeof(int)*swaps);
 11     memmove(array,temp_array,sizeof(int)*swaps);
 12 }
 13 
 14 int main()
 15 {
 16     int array[] = { 10, 20 , 30, 40, 50 };
 17     int length = 5;
 18     int swaps = 2;
 19     swap(array,length,swaps);
 20     std::copy(array,array+length,std::ostream_iterator<int>(std::cout," "));
 21 }

#include <iostream>
#include <vector>
using namespace std;
int getIndex(int index, int rot, int size)
{
int tot = index + rot;
if(tot >= size)
return tot%size;
else
return tot;
}
void swap(int* x, int *y)
{
}
void arrayRotation(vector<int> &v, int rot)
{
int lIndex = v.size() - 1;
int index = lIndex;
int tIndex = -1;
int tVar = v.at(lIndex);

do
{
tIndex = getIndex(index, rot, v.size());
//swapping the element -start
int temp = v.at(tIndex);
v.at(tIndex) = tVar;
tVar = temp;
//swapping the element - End
index = tIndex;
}while(index != lIndex);


}

int main()
{
int myints[] = {10,20,30,40, 50};
int rot =3;
std::vector<int> v(myints, myints + sizeof(myints) / sizeof(int) );
for(int i =0; i< v.size(); i++)
cout<<v.at(i)<<"\t";
cout<<endl;
arrayRotation(v,rot);
for(int i =0; i< v.size(); i++)
cout<<v.at(i)<<"\t";
cout<<endl;
return 0;
}

The rotation can be done in Linear Time, I don't think it will posiible to do less than liner because there will be a change in every element of the array.

I haven't implmented the swap function outside, did in the same function.

What is being sought out here? Do you want to predict the state of the array after n rotations or do you want to search an element in the array after it has been rotated n times?

1.first check if the array is rotated or not
2.if not rotated then count is 0
3.then check for <=n rotations
4.find its rotations times using binary search


#include<stdio.h>
int binary_search(int a[],int lb,int ub,int n,int *c)
{
int mid=lb+(((ub-lb)+1)/2);
if((mid>0)&&(a[mid]>a[mid-1])&&(mid<n)&&(a[mid]>a[mid+1]))
*c=mid;
if(!*c)
binary_search(a,lb,mid,n,c);
if(!*c)
binary_search(a,mid+1,ub,n,c);
return c;
}
int main()
{
int a[]={70,80,90,10,20,30,40,50,60};
int n=(sizeof(a)/sizeof(a[0])),c=0;
binary_search(a,0,n-1,n-1,&c);
if(a[0]<a[n-1])
{
printf("0");
return 0;
}
else if(c)
{
printf("%d",c+1);
return 0;
}
else if(a[0]>a[n-1])
{
printf("%d",n);
return 0;
}
return 0;
}

We can address this problem by searching for the index of the smallest element in the array. The original array is sorted, hence n-i+1 (i is the index of the smallest element) is the number of elements that are not in their correct position. It is an O(lg n) solution.

An O(logn) solution:

int find_head(int A[], int n)
{
    int l, r, m;
    l = 0; r = n-1;
    while (l < r) {
        m = (l+r)/2;
        if (A[m] < A[r])
            r = m;
        else if (A[m] >= A[l])
            l = m+1;
    }
    return l;
}

I didnot understood the question

/**
	 * O(logn)
	 * find no of rotations - circularly sorted array, anti-clockwise, no duplicates - binary
	 * no of rotation = index of min element
	 * @param source
	 * @param needle
	 * @return
	 */
	private int countRotationsBinary(int[] source){
		int low = 0;
		int high = source.length - 1;
		int length = source.length;
		
		while( low <= high ){
			if( source[low] <= source[high] ) return low; //case 1 (sorted array)
			int mid = ( low + high ) /  2;
			int next = (mid+1) % length;
			int prev = (mid+length-1) % length;
			if( source[mid] <= source[prev] &&  source[mid] <= source[next] )	return mid; //case 2
			if( source[mid] <= source[high] ) { high = mid - 1; } //case 3 - search left
			if( source[mid] >= source[low] ) { low = mid + 1; } //case 4 - search right
			
		}
		
		return -1;
	}

the problem can be solved by using binary search in 0(logn) time. enjoy.

public class RotateArray {

public static void main(String[] args) {
// TODO Auto-generated method stub

int [] x = {10,20,30,40,50,60,70};
getRotateArray(x, 3);

}


public static void getRotateArray(int[]y, int rotate){
for (int j = 0; j < rotate; j++) {
for (int i = y.length-1; i > 0; i--) {
int temp =y[i];
y[i] =y[i-1];
y[i-1] =temp;
}
}
for (int i = 0; i < y.length; i++) {
System.out.println(y[i]);
}

}
}