?

Log in

No account? Create an account

Previous Entry | Next Entry

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

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.

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.

See the comment count unavailable DW comments at http://mindstalk.dreamwidth.org/465263.html#comments

Profile

Phoenix
mindstalk
Damien Sullivan
Website

Latest Month

October 2017
S M T W T F S
1234567
891011121314
15161718192021
22232425262728
293031    

Tags

Powered by LiveJournal.com
Designed by Lilia Ahner