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