Problem: Write a program that will rotate a given array of size n by d elements.
eg: 1 2 3 4 5 6 7 and d = 3
Output : 4 5 6 7 1 2 3
Method 1:
For rotating the array by d elements, first rotate it by 1. Move a[1] to a[0], a[2] to a[1] and so on.
Repeat the shifting process d times.
In the above example, We get [2, 3, 4, 5, 6, 7, 1] after first rotation, [ 3, 4, 5, 6, 7, 1, 2] after second rotation and [ 4, 5, 6, 7, 1, 2, 3] after third rotation.
// function to rotate array by one shifting all elements one by one void rotateByOne(int a[], int n) { int i, temp; temp = a[0]; for (i = 0; i < n-1; i++) a[i] = a[i+1]; arr[i] = temp; } // repeat above function d times to rotate array void rotateArray(int a[], int n, int d) { int i; for (i = 0; i < d; i++) rotateByOne(a, n); }
Time complexity: O(n*d)
Method 2: Using temp array
Input a[] = [1, 2, 3, 4, 5, 6, 7], d = 3 and n =7
(1) Store first d elements in a temporary array
temp[] = [1, 2, 3]
(2) Shift rest of the array
a[] = [4, 5, 6, 7, 6, 7]
(3) Store back the d elements
a[] = [4, 5, 6, 7, 1, 2, 3]
Time Complexity: O(n), Space Complexity: O(d)
Method 3: Using reversal algorithm
Using reversal algorithm, lets assume array as combination of 2 arrays say A1A2.
First, reverse the A1 then reverse A2. then reverse complete set A1A2.
Lets try to understand this with an example.
For a[] = [1, 2, 3, 4, 5, 6, 7], d = 3 and n = 7
A1 = [1, 2, 3] and A2 = [4, 5, 6, 7]
Reverse A1, we get A1′B = [3, 2, 1, 4, 5, 6, 7]
Reverse A2, we get A1′B1′ = [3, 2, 1, 7, 6, 5, 4]
Reverse complete set, we get (A1′B1′)’ = [4, 5, 6, 7, 1, 2, 3]
// reverse array from start to end void reverse(int a[], int start, int end) { int i; int temp; while(start++ < end--) { temp = a[start]; a[start] = a[end]; a[end] = temp; } } // function that will rotate array by d elements void rotateArray(int a[], int d, int n) { reverse(a, 0, d-1); reverse(a, d, n-1); reverse(a, 0, n-1); }
Time Complexity: O(n)
i think its a better algorithm..
for i =0 to n/2-1
swap(a[n/2-i],a[n/2]+i)
#include
#include
int main()
{int n;
printf("Enter size of array\n");
scanf("%d",n);
int B[n];
int A[n] ;
int k,i,j,l;
i=0;j=0;
printf("Enter values\n");
for(l=0;l < n;l++)
{
scanf(%d,A[l]);
}
printf(Enter number of element you want to rotate\n);
scanf(%d,k);
while(i < k)
{
B[n-k+i]=A[i];
i++;
}
j=n-k;
while(i < n)
{
B[n-k-j]=A[i];
i++;
j–;
}
for(i=0;i < n;i++)
{
printf(%d\n,B[i]);
}
return 0;
}
// Autor: Claudio C Rodrigues
// Data: dd/mm/aaaa
#include
#include
#include
int a[100000];
int main() {
int n, d, i;
/* Read input from STDIN. Rotate array by d elements. Print output to STDOUT */
scanf(“%d %d”,&n,&d); // n <– number of elem. d <– number of shift lefts
for(i=0;i<n;++i) scanf("%d",&a[i]); // real elements
for(i=d;i<n+d;++i) printf("%d ",a[i%n]); // print array rotacionado
return 0;
}
help me, I need a program to shift bot first and second largest element in an max heap
Help me I need a c program for left rotation of an array of size n by d positions
#include
void main()
{
int n,i,j,k,temp,a[20];
printf(“enter the n value:”);
scanf(“%d”,&n);
printf(“enter the array elements:”);
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
printf("enter the rotation:");
scanf("%d",&k);
for(i=0;i0;j–)
{
a[j]=a[j-1];
}
a[j]=temp;
}
printf(“right rotated array:”);
for(i=0;i<n;i++)
printf("%d ",a[i]);
}
can you please elaborately explain what u have written.
this logic can also be used..
while(d>0){ //d=number of rotations to be
performed
cout<<arr[(i+(n-d))%n];
}
this piece of code will also print the iterations performed at each step.