Circular Array Rotation

See the original problem on HackerRank.

Solutions

You can actually rotate the array:

in Javascript (by Alessia Bragagnolo)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
function circularArrayRotation(a, k, queries) {
  let result = [];

  while (k > 0) {
    let tmp = a.pop();
    a.unshift(tmp);
    k--;
  }

  for (let i = 0; i < queries.length; i++) {
    result.push(a[queries[i]]);
  }

  return result;
}

But… we don’t really need to rotate the array:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
int N, K, Q, idx; cin >> N >> K >> Q;
K %= N;
vector<int> arr(N);
copy_n(istream_iterator<int>(cin), N, begin(arr));
const auto diff = N-K;
while (Q--)
{
    cin >> idx;
    cout << arr[(idx+diff)%N] << endl;
}

in Python:

1
2
3
4
n, k, q = map(int, raw_input().split())
arr = map(int, raw_input().split())
for _ in range(q):
    print arr[(input() + n - k) % n]

in Haskell:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
circularArrayRotation :: [Int] -> Int -> [Int] -> [Int]
circularArrayRotation a k = fmap go
  where
    go q = a !! mod (q - k) n
    n = length a

main = do
  [_, k, _] <- fmap read . words <$> getLine
  a <- fmap read . words <$> getLine
  qs <- fmap read . lines <$> getContents
  putStr . unlines $ show <$> circularArrayRotation a k qs

in PHP (by Filippo Bello)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
<?php
function circularArrayRotation($a, $k, $queries) {
    for ($i=0; $i < count($a); $i++) {
        $c[($i + $k) % count($a)] = $a[$i];
    }

    for ($i=0; $i < count($queries); $i++) {
        $d[$i] = $c[$queries[$i]];
    }

    return $d;
}
math 
We've worked on this challenge in these gyms: modena  padua 
comments powered by Disqus