Circular Array Rotation C++ HackerRank

Question

I solved the Circular-Array-Rotation problem on HackerRank. I conceded defeat and looked at the answers given on HackerRank itself but the ones I saw used things like vectors, which are concepts I'm a noob at as my knowledge of C++ thus far extends only as far as virtual functions and classes and such (junior COE student). So here's the description of the problem:

John Watson performs an operation called a right circular rotation on an array of integers, \$a[0], a[1], \dotsc, a[n-1]\$. After performing one right circular rotation operation, the array is transformed from \$a[0], a[1], \dotsc, a[n-1]\$ to \$a[n-1], a[0], \dotsc, a[n-2]\$.

Watson performs this operation \$k\$ times. To test Sherlock's ability to identify the current element at a particular position in the rotated array, Watson asks \$q\$ queries, where each query consists of a single integer, \$m\$, for which you must print the element at index \$m\$ in the rotated array (i.e., the value of \$a[m]\$).

Input Format

The first line contains 3 space-separated integers, \$n\$, \$k\$, and \$q\$, respectively.

The second line contains \$n\$ space-separated integers, where each integer \$i\$ describes array element \$a[i]\$ (where \$0 \le i < n\$). Each of the \$q\$ subsequent lines contains a single integer denoting \$m\$.

Constraints

\begin{align*} 1 &\le n &&\le 10^5 \\ 1 &\le a[i] &&\le 10^5 \\ 1 &\le k &&\le 10^5 \\ 1 &\le q &&\le 500 \\ 0 &\le m &&\le n - 1 \end{align*}

Output Format

For each query, print the value of the element at index \$m\$ of the rotated array on a new line.

Sample Input

3 2 3 1 2 3 0 1 2 

Sample Output

2 3 1 

Explanation

After the first rotation, the array becomes \$[3,1,2]\$. After the second (and final) rotation, the array becomes \$[2,3,1]\$.

Let's refer to the array's final state as array \$b\$. For each query, we just have to print the value of \$b[m]\$ on a new line:

1. \$m = 0\$, so we print 0 on a new line.
2. \$m = 1\$, so we print 1 on a new line.
3. \$m = 2\$, so we print 2 on a new line.

This is my code, sadly it only works for a few of the test cases, and times out for the others. Any feedback welcome, including suggestions on learning new methods or anything.

int n; int k; int q; cin >> n >> k >> q; int *arr = new int[n]; int *query = new int[q]; for (int i = 0; i < n; i++) { cin >> arr[i]; } for (int j = 0; j < q; j++) { cin >> query[j]; } int *arr2 = new int[n]; int count = 0; while (count < k) { int temp = arr[n - 1]; for (int j = 1; j < n; j++) { arr2[j] = arr[j - 1]; } arr2[0] = temp; for (int j = 0; j < n; j++) { arr[j] = arr2[j]; } count++; } for (int m = 0; m < q; m++) { cout << arr2[query[m]] << endl; } 

Answer 1

Rather than performing a rotation k times, perform one rotation of k places.

So, you have an array [5, 4, 3, 2, 1] and want to rotate it 3 places:

• Create a new array containing the results
• Start iterating through the array, calculating the index in the new array and assigning the values
• Starts at i = 0 (value 5). Wants a rotation of 3, so newArray[i + k] = array[i]
• Continues this up to i = 2, where we find a hitch: newArray[i + k] = array[i], a.k.a. newArray[5] = array[2], so out of bounds. Uh oh!
• We must make the assignment cycle around, so we must use mod with the size of the array to produce a single iteration over the initial array with this: newArray[(i + k) % n] = array[i]

Answer 2

You should definitely familiarize with the 'modulus' operator % – calculating the 'un-rotated' (original) position of the item to find is waaay faster than performing a hundred thousand rotations (k is up to \$10^5\$) of one hundred thousand-item array (n up to \$10^5\$).
It is even faster than a single rotation.

But that is for StackOverflow rather than CodeReview...

Answer 3

Might I recommend the following design to you?

class RotatedArray { vector<int> data; int shift; public: RotatedArray(const vector<int>& _data) : data(_data) {} //maybe do the constructor over a file or with a move, that would be more efficient rotate(const unsigned int amount_rotations = 1){ shift -= amount_rotations; } const int& operator[](const size_t i) const { return data[((int) i + shift) % data.size()]; } }; 

While there were already answers that recommend the basic strategy of using modulo instead of actually rotating, nobody suggested using a class. If you have some behavior that something should have, then the OO way is to make it a class.

It might seems that using a class is a minor addition, but if you want to do C++, then go with classes. Right now, if somebody would not know what your code is supposed to do, he'd have to spend quite some time thinking before doing anything with it. Also, the original exercise might call things like n, k and q, but I strongly recommend to give them descriptive names, like size or queries. In any case, your main should contain like 3 to 5 lines and not a big procedural approach.

Wrote the implementations in the header here for simplicity of this answer, of course those should be written in a source file.