Rotate an array left by k positions in place, using O(1) extra memory.
Solution
main.c
#include <stdio.h>
static void reverse(int *a, int i, int j) {
while (i < j) {
int t = a[i];
a[i++] = a[j];
a[j--] = t;
}
}
void rotate_left(int *a, int n, int k) {
k %= n;
reverse(a, 0, k - 1); /* reverse the first k */
reverse(a, k, n - 1); /* reverse the rest */
reverse(a, 0, n - 1); /* reverse everything */
}
int main(void) {
int a[] = {1, 2, 3, 4, 5, 6, 7};
rotate_left(a, 7, 3);
for (int i = 0; i < 7; i++)
printf("%d ", a[i]);
printf("\n");
return 0;
}
Output Verified by compiling and running
4 5 6 7 1 2 3
Three reversals do the rotation: [3 2 1 | 7 6 5 4] → reverse all → 4 5 6 7 1 2 3. Each element moves a constant number of times: O(n) time, no second array. k %= n handles k larger than n.
Share your method, a shortcut, or ask about a step you didn't follow.
No comments yet. Be the first to share your solution!
We use Google Analytics cookies to see how LearnFrenzy is used and make it better, and Google AdSense to keep it free.
No analytics or ad cookies are set until you accept. Privacy Policy
·
Discussion & Comments 0
Share your method, a shortcut, or ask about a step you didn't follow.
No comments yet. Be the first to share your solution!