![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
Entry tags:
fast array rotation
A simple problem I'd never had occasion to think much before, before I saw a sample coding problem.
How to rotate the elements of an N-element array by k spaces? An obvious way is to shuffle it one space, k times, but that's slow, O(N*k). Faster, which I saw about as soon as I thought about performance, is to use a second array B, where B[(i+k)%N] = A[i]. But that takes O(N) extra space. Can you do better?
Yes, as I realized at 5am. For each element A[i], move it to A[(i+k)%N]. O(N) time, O(1) extra space. Can't beat that!
Except some mildly tricky math intervenes: the natural approach only works if N and k are relatively prime. A more general solution is
Despite looking like a double loop, it's still O(N), with g*N/g iterations.
[2020 Edit: Looking back... I find this less than clear. I went to the code to make sure I got it right.
]
I've also learned that C++ has a gcd function now. std::experimental::gcd, in the header experimental/numeric. C++17 moves it out of experimental but even g++ isn't doing that by default.
The really annoying this is that this is the sort of solution that comes naturally to me lying in bed, with little conscious effort, but that I'd likely fail to get in a whiteboard session or timed coding test, due to stress dropping my working IQ.
How to rotate the elements of an N-element array by k spaces? An obvious way is to shuffle it one space, k times, but that's slow, O(N*k). Faster, which I saw about as soon as I thought about performance, is to use a second array B, where B[(i+k)%N] = A[i]. But that takes O(N) extra space. Can you do better?
Yes, as I realized at 5am. For each element A[i], move it to A[(i+k)%N]. O(N) time, O(1) extra space. Can't beat that!
Except some mildly tricky math intervenes: the natural approach only works if N and k are relatively prime. A more general solution is
let g = gcd(N,k)
for i in [0,g)
for j in [0, N/g)
shuffle element k spaces
Despite looking like a double loop, it's still O(N), with g*N/g iterations.
[2020 Edit: Looking back... I find this less than clear. I went to the code to make sure I got it right.
#ar = (array)
g = gcd(N, k)
for i in range(g):
cur = ar[i]
for j in range(1, N//g+1):
temp = ar[(i + j*k) % N]
ar[(i + j*k) % N] = cur
cur = temp
]
I've also learned that C++ has a gcd function now. std::experimental::gcd, in the header experimental/numeric. C++17 moves it out of experimental but even g++ isn't doing that by default.
The really annoying this is that this is the sort of solution that comes naturally to me lying in bed, with little conscious effort, but that I'd likely fail to get in a whiteboard session or timed coding test, due to stress dropping my working IQ.