Rotate the array to the left (counter-clockwise direction) by D steps in O(n) time
- Time complexity : O(n)
- Space Complexity : O(1)
If D is the number of steps and N is the number of element in the array. First find the D%N to reduce the number of steps. If D>N ,then we have to same steps D/N times.
Now partition the array taking d as pivot. Reverse the array from arr[0] to arr[d-1] and arr[d] to arr[n-1].
Eg : If the array is
1 2 3 4 5, where d=2 and n=5
after taking d as pivot the new array will be 2 1 5 4 3
Now reverse the whole array . Over all time complexity will be O(n)
_____________________
static void rotateArr(int arr[], int d, int n){d = d%n;int temp;for(int i=0;i<d/2;i++){temp = arr[i];arr[i] = arr[d-1-i];arr[d-1-i] = temp;}for(int i=d;i<(n+d)/2;i++){temp = arr[i];arr[i] = arr[n+d-1-i];arr[n+d-1-i] = temp;}for(int i=0;i<n/2;i++){temp = arr[i];arr[i] = arr[n-1-i];arr[n-1-i] = temp;}}
No comments:
Post a Comment