2
\$\begingroup\$

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;
}
\$\endgroup\$
5
  • \$\begingroup\$ Too long to compile is not a thing for these challenges, you mean it takes too long to run, right? Anyway, you know the code doesn't work - broken code is off-topic here. Please fix the code before requesting review - otherwise answers will consist of "You should fix the bugs" ... which won't teach you anything for next time. \$\endgroup\$
    – Pimgd
    Commented Aug 17, 2016 at 14:46
  • \$\begingroup\$ The code is terribly inefficient, but is not broken: it should produce correct results given sufficient time. I think this question should be reopened. \$\endgroup\$
    – Jaime
    Commented Aug 17, 2016 at 15:01
  • 8
    \$\begingroup\$ Please include the problem statement, not a picture of it. \$\endgroup\$ Commented Aug 17, 2016 at 17:11
  • \$\begingroup\$ Here's the original problem at HackerRank: hackerrank.com/contests/feb14/challenges/… \$\endgroup\$
    – CiaPan
    Commented Aug 19, 2016 at 6:00
  • \$\begingroup\$ And here's the same problem discussed at StackOverflow about 4 days ago: stackoverflow.com/questions/38437484/… \$\endgroup\$
    – CiaPan
    Commented Aug 19, 2016 at 6:02

3 Answers 3

6
\$\begingroup\$

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]
\$\endgroup\$
1
  • 2
    \$\begingroup\$ Rather than performing ANY rotation familiarize with the % operator... \$\endgroup\$
    – CiaPan
    Commented Aug 18, 2016 at 8:25
5
\$\begingroup\$

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...

\$\endgroup\$
1
  • \$\begingroup\$ noted! much appreciated \$\endgroup\$
    – Joker
    Commented Aug 18, 2016 at 19:02
2
\$\begingroup\$

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.

\$\endgroup\$
8
  • \$\begingroup\$ If you have some behavior that something should have, then the OO way is to make it a class.. I don't think OO is the right way here. There are more powerful ways to extend/alter functionality of something (template specializations, special overloads, etc). I think they would behave much more naturally. The perfect example I think is std::sort: I know a lot of people who use it and have no idea how it works. But it binds two concepts together: algorithms and iterators. I think that using rotated_view would be better [continuation in next comment] \$\endgroup\$ Commented Aug 1, 2017 at 10:37
  • \$\begingroup\$ [continuation of comment above] the thing is that std::rotate() does much better job at rotating, and also is container independent. The functionality to add would be something like rotated_view, which doesn't rotate the container, but pretends that it is rotated. It could take a pair of iterators, and then return other type of iterator, which wraps around and basically creates a "feeling" of rotated view. \$\endgroup\$ Commented Aug 1, 2017 at 10:39
  • \$\begingroup\$ I think what you wanted (please correct me if I'm wrong) is to take just a reference to a vector and then pretend it is rotated. That would be specialization, of some sort, of rotated_view. \$\endgroup\$ Commented Aug 1, 2017 at 10:43
  • \$\begingroup\$ @Incomputable I try to use as less functions as possible. Especially when we have a component that we can clearly name in a class like manner, like RotatedArray. I consider C++ to be a language in which one should prefer OO style over procedural style. But I guess that this is a matter of taste. \$\endgroup\$
    – Aziuth
    Commented Aug 1, 2017 at 10:46
  • \$\begingroup\$ the rotated_view is a class too, but very peculiar one. It has only begin() and end() member functions, which return some wrapper around the underlying iterator, to make it possible to wrap around both ends. Anyway, I'll probably implement it and post one day. Should I drop a link here? \$\endgroup\$ Commented Aug 1, 2017 at 10:48

Not the answer you're looking for? Browse other questions tagged or ask your own question.