Left Rotation · Coding Gym

Solutions

A tradeoff of this problem is about using a temporary array or not. In the latter case, the steps to do are simpler because we can just copy the two parts the array: all the elements before the rotation point and then all the element after.

Here is a Java implementation:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


public static int[] rotateArray(int[] arr, int d)
{
    int n = arr.length;

    int[] rotated = new int[n];

    // Copy segments of shifted elements to rotated array:
    System.arraycopy(arr, d, rotated, 0, n - d);
    System.arraycopy(arr, 0, rotated, n - d, d);
    return rotated;
}

Here is an interesting solution using Linq in C#, by Emanuele Prato:

1
2
3
4
5
6


static int[] leftRotation(int[] a, int d)
{
    int[] array1 = a.Take(d).Reverse().ToArray();
    int[] array2 = a.Skip(d).Take(a.Length - d + 1).Reverse().ToArray();
    return array1.Concat(array2).Reverse().ToArray();
}

Doing the roation in-place is more challenging.

First of all, you may have noticed that “cheating” is possible by allocating the final array and then reading the elements in the final positions - by Roberto Melis:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


vector<int> values(n);
// reading to 'd'
for (int i = 0; i < d; ++i)
{
    cin >> values[n-d+i];
}
// reading from 'd' to the end
for (int i = 0; i < n-d; ++i)
{
    cin >> values[i];
}

for (auto & v : values)
{
    cout << v << " ";
}

The problem of rotation can be solved by doing a “reverse” operation three times. Here is the core part, by Roberto Melis:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


vector<int> values(n);
copy_n(istream_iterator<int>(cin), n, begin(values));

auto swap = [&values](int from, int to)
{
    for (int i = from; i < from+(to-from)/2; ++i)
        std::swap(values[i], values[to-1-(i-from)]);
};

swap(0, d);
swap(d, n);
swap(0, n);

copy(begin(values), end(values), ostream_iterator<int>(cout, " "));

swap can be rewritten in terms of std::reverse:

1
2
3
4
5
6
7
8


vector<int> values(n);
copy_n(istream_iterator<int>(cin), n, begin(values));

reverse(begin(v), begin(v)+d);
reverse(begin(v)+d, end(v));
reverse(begin(v), end(v));

copy(begin(values), end(values), ostream_iterator<int>(cout, " "));

In Haskell:

1

leftRotation d arr = reverse ( ( reverse ( take d arr ) ) ++ ( drop d arr ) )

Actually, in C++ we can replace the whole logic with std::rotate:

1
2
3
4
5
6
7
8


int d;
cin >> d >> d;
vector<int> v{istream_iterator<int>(cin), istream_iterator<int>()};
if (d != v.size())
{
    rotate(begin(v), begin(v)+d, end(v));
}
copy(begin(v), end(v), ostream_iterator<int>(cout, " "));

If we can stream to the output without using a function returning an array, we can just stream the two chunks at ranges [d, n - d) and [0, d).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


#include <iostream>
#include <vector>
#include <iterator>
#include <algorithm>
using namespace std;
int main() {
    int n, d;
    cin >> n >> d;
    vector<int> values(n);
    copy_n(istream_iterator<int>(cin), n, begin(values));
    copy_n(begin(values) + d, n - d, ostream_iterator<int>(cout, " "));
    copy_n(begin(values)    , d    , ostream_iterator<int>(cout, " "));
}

If data is not an array but a linked list (as std::list) we can easily change list internal pointers with slice. No elements are copied in this case.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


#include <iostream>
#include <list>
#include <iterator>
#include <algorithm>
using namespace std;

void rotate_left(list<int>& v, int d) {
    v.splice(v.begin(), v, next(v.begin(), d), v.end());
}

int main() {
    int n, d;
    cin >> n >> d;
    list<int> v;
    copy_n(istream_iterator<int>(cin), n, back_inserter(v));
    rotate_left(v, d);
    copy(begin(v), end(v), ostream_iterator<int>(cout, " "));
}

In Haskell, the solution is very terse: just concatenates two list, one where d elements have been dropped, and one where d elements have been taken.

1
2
3
4
5
6


leftRotation :: Int -> [Int] -> [Int]
leftRotation d arr = drop d arr ++ take d arr

main = do
  (d:arr) <- ( fmap read ) . drop 1 . words <$> getContents
  putStr $ unwords $ fmap show $ leftRotation d arr

Due to lazyness of Haskell, the list arr is not copyied, but streamed directly to the IO. A similar solution may be written in C++ like that:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


#include <iostream>
#include <list>
#include <iterator>
#include <algorithm>
using namespace std;

void drop(std::ostream& os, const list<int>& v, int d) {
    copy(next(begin(v), d), end(v), ostream_iterator<int>(cout, " "));
}

void take(std::ostream& os, const list<int>& v, int d) {
    copy(begin(v), next(begin(v), d), ostream_iterator<int>(cout, " "));
}

int main() {
    int n, d;
    cin >> n >> d;
    list<int> v;
    copy_n(istream_iterator<int>(cin), n, back_inserter(v));
    drop(cout, v, d);
    take(cout, v, d);
}

Anyway, this problem is instructive. We can try rolling our own implementation of array rotation or understand that it’s possible to use three calls to reverse.

patterns