Rohan Shahane - 1 year ago 102

C++ Question

I'm solving this problem on Hackerrank.

John Watson performs an operation called a right circular rotation on an array of integers, [a[0],a[ 1]......a[n]].After performing one right circular rotation operation, the array is transformed from [a[0],a[ 1]......a[n]] 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 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[n] (where 0<=i

Output Format

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

`#include <cmath>`

#include <cstdio>

#include <vector>

#include <iostream>

#include <algorithm>

using namespace std;

int main() {

/* Enter your code here. Read input from STDIN. Print output to STDOUT */

int n,k,q,temp;

cin>>n>>k>>q; //Input of n,k,q;

int arr[n],qur[q];

for(int i=0;i<n;i++) //Input of array

{

cin>>arr[i];

}

for(int i=0;i<q;i++) //Input of query numbers

{

cin>>qur[i];

}

for(int z=0;z<k;z++)

{

temp = arr[n-1];

for(int i=n-1;i>0;i--)

{

arr[i]=arr[i-1];

}

arr[0]=temp;

}

for(int i=0;i<q;i++)

{

cout<<arr[qur[i]]<<endl;

}

return 0;

}

The code's logic seems to be flawless. I'm a newbie.Thanks in advance.

Answer Source

The reason is that you don't really need to perform the rotation, you can use The Ancient Power of Mathematics.

(Performing the rotation can require 10 billion `arr[i]=arr[i-1]`

s, and doing that 500 times would take a while.)

If you start with the sequence

```
Element: | 12 | 34 | ... | 56 | 78 | (1)
Index: 0 1 ... k-1 k
```

and right-rotate by one, you get

```
Element: | 78 | 12 | 34 | ... | 56 | (2)
Index: 0 1 2 ... k
```

or, changing the viewpoint just a little bit:

```
Element: | 12 | 34 | ... | 56 | 78 | (3)
Index: 1 2 ... k 0
```

There's a fairly simple relationship between the indices of the elements in (1) and (3), and you only need some arithmetic to get from one to the other.

Discovering the relationship and performing the arithmetic left as an exercise.