Problem
Given an array of integers, you need to rotate it by k times.
Sample Input
[1, 2, 3] k=1
Sample Output
[2, 3, 1]
Approach 1
We can place the first k elements in some other array and shift remaining elements to the beginning. Later, we can insert the first k elements at the last. The approach takes O(N) time and O( k ) auxiliary space.
C
#include <stdio.h> voidsolve(int arr[], int k, int n) { int auxArray[k]; for (int i = 0; i < k; i++) { auxArray[i] = arr[i]; } for (int i = k; i < n; i++) { arr[i-k] = arr[i]; } for (int i = n-k; i < n; i++) { arr[i] = auxArray[i-(n-k)]; } } intmain() { int arr[] = { 1, 2, 3 }; int k = 1; int n = sizeof(arr)/sizeof(arr[0]); solve(arr, k, n); for (int i = 0; i < n; i++) { printf("%d ", arr[i]); } return0; }
Output
2 3 1
Approach 2
If we reverse first k elements, then the remaining elements and then the entire array, we may observe that this will always give the required array. This approach takes O(N) time and O(1) auxiliary space.
C
#include <stdio.h> voidreverseHelper(int arr[], int low, int high) { for (int i = low, j = high; i < j; i++, j--) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } } voidsolve(int arr[], int k, int n) { reverseHelper(arr, 0, k - 1); reverseHelper(arr, k, n - 1); reverseHelper(arr, 0, n - 1); } intmain(void) { int arr[] = { 1, 2, 3 }; int k = 1; int n = sizeof(arr)/sizeof(arr[0]); solve(arr, k, n); for (int i = 0; i < n; i++) { printf("%d ", arr[i]); } return0; }
Output
2 3 1
C++
#include <bits/stdc++.h> usingnamespacestd; voidreverseHelper(int arr[], int low, int high) { for (int i = low, j = high; i < j; i++, j--) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } } voidsolve(int arr[], int k, int n) { reverseHelper(arr, 0, k - 1); reverseHelper(arr, k, n - 1); reverseHelper(arr, 0, n - 1); } intmain(void) { int arr[] = { 1, 2, 3 }; int k = 1; int n = sizeof(arr)/sizeof(arr[0]); solve(arr, k, n); for (int i = 0; i < n; i++) { cout<<arr[i]<<" "; } return0; }
Output
2 3 1
Python
defswap(arr, i, j): temp = arr[i] arr[i] = arr[j] arr[j] = temp defreverse(arr, start, finish): (i, j) = (start, finish) while i < j: swap(arr, i, j) i = i + 1 j = j - 1 defsolve(arr, k): reverse(arr, 0, k - 1) reverse(arr, k, len(arr) - 1) reverse(arr, 0, len(arr) - 1) arr = [1, 2, 3] k = 1 solve(arr, k) print(arr)
Output
2 3 1
People are also reading:
Leave a Comment on this Post