current community

your communities

more stack exchange communities

company blog
Stack Exchange Inbox Reputation and Badges
tour help
up vote 1 down vote favorite

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.. enter image description here

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;
}
share|improve this question
    
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. – Pimgd Aug 17 '16 at 14:46
    
The code is terribly inefficient, but is not broken: it should produce correct results given sufficient time. I think this question should be reopened. – Jaime Aug 17 '16 at 15:01
5  
Please include the problem statement, not a picture of it. – Mat's Mug♦ Aug 17 '16 at 17:11
    
Here's the original problem at HackerRank: hackerrank.com/contests/feb14/challenges/… – CiaPan Aug 19 '16 at 6:00
    
And here's the same problem discussed at StackOverflow about 4 days ago: stackoverflow.com/questions/38437484/… – CiaPan Aug 19 '16 at 6:02
up vote 2 down vote

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]
share|improve this answer
    
Rather than performing ANY rotation familiarize with the % operator... – CiaPan Aug 18 '16 at 8:25
    
thank you so much, i have an inkling on what to do now! – Joker Aug 18 '16 at 19:02
up vote 1 down vote

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

But that is for StackOverflow rather than CodeReview...

share|improve this answer
    
noted! much appreciated – Joker Aug 18 '16 at 19:02

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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