1
\$\begingroup\$

I'm a first time poster. I conceded defeat and looked at the answers given on hackkerank 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 this is the question..

John Watson performs an operation called a right circular rotation on an array of integers, [a[0], a[1], … a[n-1]]. After performing one right circular rotation operation, the array is transformed from [a[0], a[1], … a[n-1]] to [a[n-1], a[0], … 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 ≤ i < n). Each of the q subsequent lines contains a single integer denoting m.

Constraints

  • 1 ≤ n ≤ 10^5
  • 1 ≤ a[i] ≤ 10^5
  • 1 ≤ k ≤ 10^5
  • 1 ≤ q ≤ 500
  • 0 ≤ mn - 1

Output Format

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

Sample Input 0

3 2 3
1 2 3
0
1
2

Sample Output 0

2
3
1

Explanation 0

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 on a new line.
  2. m = 1, so we print on a new line.
  3. m = 2 , so we print 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\$
  • \$\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 Aug 17 '16 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 Aug 17 '16 at 15:01
  • 8
    \$\begingroup\$ Please include the problem statement, not a picture of it. \$\endgroup\$ – Mathieu Guindon Aug 17 '16 at 17:11
  • \$\begingroup\$ Here's the original problem at HackerRank: hackerrank.com/contests/feb14/challenges/… \$\endgroup\$ – CiaPan Aug 19 '16 at 6:00
  • \$\begingroup\$ And here's the same problem discussed at StackOverflow about 4 days ago: stackoverflow.com/questions/38437484/… \$\endgroup\$ – CiaPan Aug 19 '16 at 6:02
5
\$\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\$
  • 2
    \$\begingroup\$ Rather than performing ANY rotation familiarize with the % operator... \$\endgroup\$ – CiaPan Aug 18 '16 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\$
  • \$\begingroup\$ noted! much appreciated \$\endgroup\$ – Joker Aug 18 '16 at 19:02
1
\$\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\$
  • \$\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\$ – Incomputable Aug 1 '17 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\$ – Incomputable Aug 1 '17 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\$ – Incomputable Aug 1 '17 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 Aug 1 '17 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\$ – Incomputable Aug 1 '17 at 10:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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