Left Rotation

See the original problem on HackerRank.

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.

We've worked on this challenge in these gyms: modena  padua  milan 
comments powered by Disqus