varun
BAN USER#include<iostream.h>
#include<conio.h>
int a[]={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15};
int n=sizeof(a)/sizeof(a[0]);
int count=0,row_size=n/3;
void swap(int i,int j)
{
int temp=a[i];
a[i]=a[j];
a[j]=temp;
}
void main()
{
clrscr();
int j=1,loc=j;
for(int i=1;i<n-1;i++)
{
loc=(3*loc+loc/row_size)%n;
if(j!=loc)
swap(j,loc);
else
{
j++;
loc=j;
}
}
for(int pos=0;pos<n;pos++)
cout<<" "<<a[pos];
getch();
}
#include<iostream.h>
#include<conio.h>
int a[]={1,2,3,4,5,6,7,8,9,10,11,12};
int n=sizeof(a)/sizeof(a[0]);
int count=0,row_size=n/3;
void swap(int i,int j)
{
int temp=a[i];
a[i]=a[j];
a[j]=temp;
}
void main()
{
clrscr();
int j=1,loc=j;
for(int i=1;i<n-1;i++)
{
loc=(3*loc+loc/row_size)%n;
if(j!=loc)
swap(j,loc);
else
{
j++;
loc=j;
}
}
for(int pos=0;pos<n;pos++)
cout<<" "<<a[pos];
getch();
}
the question can be rephrased as
find i and j such that a[i]-a[j] is maximum and i>j...now this can be solved in O(n)
int n=10,min=arr[0],max=-32767 ;
for(int i=1;i<n;i++)
{
if(arr[i]<min)
{
min=arr[i];
continue;
}
if(arr[i]-min>max)
max=arr[i]-min;
}
cout<<"MAX DIFFERENCE IS : "<<max;
o(n) complexity
- varun July 17, 2012no extraa space.
minor optimisation required, in the for loop instead of j++ j should be set to index that is not processed yet.
approach is simple
for elements(i) from 0 to n/3 new position is (3*i)%n
for elemens from n/3+1 to 2n/3 new position is (3*i+1)%n
for 2n/3+1 to n is (3*i+2)%n