Dough's algorithm also does 1 swap per item, guaranteed. It's equivalent to
Doug Harrison [MVP] wrote:
This what I came up with
template<class T> void Rotate(std::vector<T>& a, int n)
{
size_t M = a.size();
if(M <= 1) return;
size_t N = ( n >= 0 ? n%M : M - 1 - (-1 - n)%M );
size_t m = 0; // running number of correct entries
for(size_t i = 0; m < M; i++, m++)
for(size_t j = (i + N)%M; j != i; j = (j + N)%M, m++)
std::swap(a[i], a[j]);
}
GCD is maybe lurking in there somewhere, but not explicitly.
Good job. Here's the trick answer:
template<class T> void Rotate2(std::vector<T>& a, int n)
{
// Parameter validation omitted.
if (n < 0)
n = -n;
else
n = a.size()-n;
std::reverse(a.begin(), a.begin()+n);
std::reverse(a.begin()+n, a.end());
std::reverse(a.begin(), a.end());
}
And I was worried that using std::swap() was cheating...
The trick answer is cute, but being forced to come up with that could lead
to a very long interview...
Given that any method must reduce to a sequence of swaps (true I think), I
believe my brute force method uses the minimum possible number of swaps.
Each swap places one entry in the correct position, except for the last
swap in each cycle, which places two entries. (this is why m++ appears in
both loops).
--
David Wilkinson
Visual C++ MVP