# Circular Array Rotation

# Circular Array Rotation

piyush121 + 56 comments Easy and fast as hell --> O(n) time and O(1) Space........

public static void main(String[] args) { Scanner in = new Scanner(System.in); int N = in.nextInt(); int K = in.nextInt(); int Q = in.nextInt(); int rot = K % N; int[] arr = new int[N]; for (int i = 0; i < N; i++) arr[i] = in.nextInt(); for (int i = 0; i < Q; i++) { int idx = in.nextInt(); if (idx - rot >= 0) System.out.println(arr[idx - rot]); else System.out.println(arr[idx - rot + arr.length]); } }

Thanks for the votes guys. I never thought my solution would be on the top of the discussion forums. Anyways here is the

`mod`

based solution which many people found useful. Godspeed!public static void main(String[] args) { Scanner in = new Scanner(System.in); int n = in.nextInt(); int k = in.nextInt(); int q = in.nextInt(); int[] a = new int[n]; for(int a_i=0; a_i < n; a_i++){ a[a_i] = in.nextInt(); } for(int a0 = 0; a0 < q; a0++){ int m = in.nextInt(); System.out.println(a[(n - (k % n)+ m) % n]); } }

jfuji6 + 2 comments I did something similar, but I used mod in case

K > arr.lenth + idx.

ZEUS_DEVELOPER + 0 comments [deleted]scorpionk + 1 comment same here. I know it's too late to reply :P

chikithapaleti99 + 1 comment [deleted]Free_Electron + 0 comments [deleted]

c650Alpha + 1 comment Ah. I was doing some weird modular arithmetic, which led to funky outcomes for the unknown test cases.

Dinesh1306 + 3 comments [deleted]roman_balzer + 6 comments In your solution, you could use another modular arithmetic, to ensure the index stays within the boundaries of the array.

`queries.forEach(m => { // Modulo to stay inside the boundaries of the array console.log(arr[(n+m-k)%n]); });`

Dinesh1306 + 2 comments In my solution the index are within the boundaries.

rn27in + 0 comments Thanks a ton Dinesh. Beautiful solution. I initially used brute force without understanding the rotation pattern.

Learnt something new. Your blog is really good

Cheers

hackernitp + 12 comments #include <map> #include <set> #include <list> #include <cmath> #include <ctime> #include <deque> #include <queue> #include <stack> #include <string> #include <bitset> #include <cstdio> #include <limits> #include <vector> #include <climits> #include <cstring> #include <cstdlib> #include <fstream> #include <numeric> #include <sstream> #include <iostream> #include <algorithm> #include <unordered_map> using namespace std; int main(){ int n; int k; int q; cin >> n >> k >> q; vector<int> a(n); for(int a_i = 0;a_i < n;a_i++){ cin >> a[a_i]; } for(int i=0;i<k;i++){ for(int j=0;j<n;j++){ if(j+1!=n) { a[j+1]=a[j]; } else { a[0]=a[n-1]; } } } for(int a0 = 0; a0 < q; a0++){ int m; cin >> m; cout<<a[m]<<endl;} return 0; }

can you plz tell me what is wrong with my code???

JamesTre + 0 comments Hi, dk201966. Probably you are facing problems because the order you are doing the changes. If you copy the value from the 1st position to the 2nd one and, after this, you copy the 2nd to the 3rd, at the end you will have all the positions with the 1st value. And don't forget saving the last value before overwriting it! PS: you'll probably face other issues with this challenge...

pratikgk98 + 1 comment The main problem in the code is the order of the for loop used for rotating the elenets in the array. You should store the last element value in some temporary variable..and then use a decreasing counter in the mentioned for loop ..then u can store the value in temporary variable to the first element The error in ur code of overwriting values is eleminated by this code!👍

upendra28 + 1 comment why my code gives wrong answers ...?

vector <int> circularArrayRotation(vector <int> a, vector <int> m,int n,int k, int q) { while(k!=0) { int end=a[n-1]; for(int i=n-2;i>=0;i--) { a[i+1]=a[i]; } a[0]=end; k--; } return a; }

sankarasettyavi1 + 0 comments you need to return q not a.

mykz950 + 0 comments if(j+1!=n-1)

Saurav_Gaikwad1 + 0 comments in your code there is assignment of values....shifting of values is absent..

S_A_G + 0 comments hi Change your condition as a[j-1]=a[j]; and j=n-1;j>=0;j-- in for loop

vikram777 + 0 comments your code is wrong due to elae statement

kusaalpokharel + 0 comments I did the same and realized the values of the elements of the array that you assign later has already replaced the other element in the array. For eg: a[1]=a[0] then a[2]=a[1]=a[0] which is equal to each other

wildmud + 1 comment #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,i,s=0,e=0, t=0,b; cin>>n>>k>>q; int a[n]; for(i=0;i<n;i++) { cin>>a[i]; } k=k%n; s=0,e=n-k-1; while(s<e) { t=a[s]; a[s]=a[e]; a[e]=t; s++;e--; } s=n-k,e=n-1; while(s<e) { t=a[s]; a[s]=a[e]; a[e]=t; s++;e--; } s=0,e=n-1; while(s<e) { t=a[s]; a[s]=a[e]; a[e]=t; s++;e--; } for(i=0;i<q;i++) { cin>>b; cout<<a[b]<<endl; } return 0; }

rvrishav7 + 0 comments faster than urs i guess.. happy coding #include<bits/stdc++.h> using namespace std; int main() { long long int k,n,q; cin>>n>>k>>q; k=k%n; long long int i,ar[n],x,s=0; for(i=0;i<n;i++) cin>>ar[i]; for(i=1;i<=q;i++) { cin>>x; s=n-k+x; if(s<n) cout<<ar[s]<<endl; else if(s>=n) { s=s-n; cout<<ar[s]<<endl; }} return 0; }

rvrishav7 + 1 comment #include<bits/stdc++.h> using namespace std; int main() { long long int k,n,q; cin>>n>>k>>q; k=k%n; long long int i,ar[n],x,s=0; for(i=0;i<n;i++) cin>>ar[i]; for(i=1;i<=q;i++) { cin>>x; s=n-k+x; if(s<n) cout<<ar[s]<<endl; else if(s>=n) { s=s-n; cout<<ar[s]<<endl; }} return 0; }

it will work

NiceBuddy + 0 comments simpler one:

#include <iostream> #include <vector> #include <algorithm> #include <iterator> int main() { int n; std::cin >> n; // array size int k; std::cin >> k; //no of rotations int q; std::cin >> q; std::vector<int> vec; vec.reserve(n); std::copy_n(std::istream_iterator<int>(std::cin), n, back_inserter(vec)); k %= n; k = n-k; std::rotate(vec.begin(), vec.begin()+k,vec.end()); while(q--) { int index; std::cin >> index; std::cout << vec[index] << std::endl; } return 0; }

rvrishav7 + 0 comments refer to my code

rvrishav7 + 0 comments #include<bits/stdc++.h> using namespace std; int main() { long long int k,n,q; cin>>n>>k>>q; k=k%n; long long int i,ar[n],x,s=0; for(i=0;i<n;i++) cin>>ar[i]; for(i=1;i<=q;i++) { cin>>x; s=n-k+x; if(s<n) cout<<ar[s]<<endl; else if(s>=n) { s=s-n; cout<<ar[s]<<endl; }} return 0; }

refer this

piyushb9 + 1 comment it is failing for one case when modulo is used, any help?

Dinesh1306 + 3 comments I don't know why you guys are having problem. I have submitted my solution without any problem.

Anyway if you are having issues than you should upload you code than only i will know what the problem is.

piyushb9 + 6 comments i actually tried running the code in eclipse, and it is matching the expected output, expect in the last case where it doesnot return the result before enter is pressed, as when the return key is pressed the output becomes fully correct.

here is my code----------------------

import java.io.

*; import java.util.*;public class Solution {

`public static void main(String[] args) { Scanner s1=new Scanner(System.in); int n=s1.nextInt(); int k=s1.nextInt(); int q=s1.nextInt(); int a[]=new int[n]; for(int i=0;i<n;i++) { a[i]=s1.nextInt(); } for(int i=0;i<q;i++) { int m=s1.nextInt(); System.out.println(a[(n-k+m)%n]); } }`

}

piyushb9 + 0 comments Same problem in another solution.

Dinesh1306 + 1 comment Try this solution it will work

piyushb9 + 2 comments I am not concernerd with the working of the solution, the issue is why is it not working in that particular case, what is the issue? because i am facing the same issue in another problem which is Bigger is Greater in the implementation section.

Dinesh1306 + 0 comments [deleted]Dinesh1306 + 1 comment I can't see any problem in your code. And your code is working fine, though i haven't run it on eclipse but i have tried it on an online compiler and it gave me the correct output.

comandorubogdan + 0 comments This one is very good but, for the case when k is much more bigger than n it is not working, because an arrayoutofboundException will occure.

maybe this will help

`if (m-k%n < 0) { posValue = m-k%n+n; } else posValue = m-k%n; System.out.println(a[posValue]);`

shuvikash + 1 comment Add one line k=k%n; before second loop start then you'll pass all the test.

bpalaciosa + 0 comments Thank you

vedesh_vedu1 + 1 comment i got runtime error by using this

Vikramhunter + 1 comment same problem

JamesTre + 0 comments that's because in test case 4 the number of rotations is much bigger than the number of elements of the array. If you were really executing the rotations, it wouldn't cause any error, but would be very slow, causing errors in other cases (time out). If you use any algorythm that just subtacts the number of rotations from the size of the array, in fact you may try to access elements outside of the array. In case 4 we have an array with 515 elements which is rotated 100000 times. When I try to retrieve the 1st element, the algorythm will try to retriev the element with the index -9485(negative), giving an error of segmentation.

AKSHAY97 + 0 comments What will happen if the rotations(k) arer greater than n. For example

There are 3 number of elements i.e n=3 it performs 96 rotations i.e k=96 and m=0 ?

moucthemob + 0 comments I posted my code, if u could look at it in the comment section above that would be great!

ankur8090889931 + 0 comments # include

using namespace std; int main() { int n,k,q,temp,i,p; cin>>n>>k>>q; int a[n]; for(i=0;i>a[i]; } while(k>0) { temp=a[n-1]; for(i=n-1;i>=0;i--) { a[i]=a[i-1]; } a[0]=temp; k--; for(i=0;i>p; cout<

`return 0;`

}

problem : Terminated due to time out??

danutzp + 1 comment I came up with the exact same solution but "Test case #4" fails with a run time error. I downlowded the input and the output for this test case and ran it locally in Visual Studio (C#) and it does not fail.

pratikgk98 + 3 comments In test case 4 ..it should be noted that the value of k is greater than the no. of elements in the array(n) try using mod operator fr this problem k=k%n;👍

abbhishek971 + 0 comments Helpful!!

myselfshailander + 0 comments you figured out the time problem bro!!!! great

jsbzwork + 0 comments Thanks!!

aayushrangwala + 1 comment i tried the same thing but the test case #4 is showing runtime error

danutzp + 1 comment The strange thing is that I uploaded the same solution in C#, C++ and Java 8 and for all of them "Test case #4" fails with a run time error.

gminovska + 4 comments I encountered the same problem. The test case 4 has k bigger than n, which causes segmentation error due to index out of bounds when you do n - k. Solved the problem by setting k = k % n when it is larger than n.

elVega + 0 comments Thanks :)

malkandmms + 0 comments Thanks!

__PinkMan + 0 comments **Thanks!!**JamesTre + 0 comments Thank you a lot. I was stuck in this test case. I thought it was because of a very huge data set that could exceed maximum memory size.

hervedonner + 2 comments The "Runtime Error" for test case #4 occurs because k can be much bigger than n and in such cases the code tries to access a negative index.

For test case 4: k = 100000, n = 515.

The solution is to apply an extra modulo n on k before substracting:

queries.forEach(m => { // Modulo to stay inside the boundaries of the array console.log(arr[(n + m - (k % n)) % n]); });

vasya_bilich + 0 comments [deleted]rkarthik3cse + 0 comments Thank you.

Dinesh1306 + 1 comment Modular arithmetic is the best way to do this problem. No need to actually rotate the array. Take a look here. Circular Array Rotation

cjreasoner + 3 comments Python solution using mod:

ls = [int(x) for x in input().split()] n = ls[0] k = ls[1] queries = ls[2] array = [int(x) for x in input().split()] result = [] for q in range(queries): q = int(input()) result.append(array[q-k % n]) for e in result: print(e)

hassan2020mainul + 1 comment Here is another Python Solution:-

n,k,q = input().strip().split(' ') n,k,q = [int(n),int(k),int(q)] a = [int(a_temp) for a_temp in input().strip().split(' ')]

for i in range(q): m = int(input().strip()) print(a[(m-k)%len(a)])

msambitkumar1991 + 0 comments @hasan2020mainul can you explain the operation a(m-k)%len(a) you did?

vacky11 + 0 comments Another simple python solution

#!/bin/python import sys n,k,q = raw_input().strip().split(' ') n,k,q = [int(n),int(k),int(q)] a = map(int,raw_input().strip().split(' ')) a = a[n-(k%n):n]+a[0:n-(k%n)] for a0 in xrange(q): m = int(raw_input().strip()) print a[m]

vasilij_kolomie1 + 0 comments what is the faster?

def circularArrayRotation(a, k, queries):

a = a[-k:] + a[:-k]

return [a[i] for i in queries]

rwan7727 + 0 comments `int n; int k; int q; cin >> n >> k >> q; int a[n]; for (int i=0;i<n;i++) cin >> a[i]; int dest=k%n; int b[n]; for (int i=0;i<n;i++) { b[dest++]=a[i]; if (dest==n) dest=0; } for (int i=0;i<q;i++) { int m; cin >> m; cout << b[m] << endl; }`

sj_ali + 2 comments Can you please explain your solution ? why are you taking mod here ?

Hiren_Italiya + 2 comments he's doing mod caz after n rotation all elements will come at same position as starting point.

HuangZhenyang + 0 comments Oh!So that is what it is!I got it!Thanks!

HuangZhenyang + 0 comments And this idea will reduce the time ,right?

guitarman + 0 comments Java mod solution:

for(int i = 0; i < numQueries; i++) { System.out.println(array[(arraySize + (in.nextInt() - (numRotations % arraySize))) % arraySize]); }

karthik1301 + 1 comment Failed for one test case.

anuj_pancholi_1 + 2 comments Test case 4? Segmentation fault?

karthik1301 + 1 comment Yes

anuj_pancholi_1 + 2 comments Here's what worked for me in C++. After taking values of n and k:

while(k greater than n)k=k-n;

The value of k can be several times greater than n, so by putting this can lead to referencing an index in the array greater than n, which causes segmentation fault. And the output will be correct because performing 5 rotations in an array of 4 elements is same as performing 1 rotation.

astromahi + 2 comments you could use k=k%n, what if the k is doulble or trible the size of n. subtraction always reduce one rotation.

Consider if k = 3n => k = 3n -n => k = 2n. but in case of modular it reduces to n rotation. k = 3n => k = 3n%n => k = 0.

anuj_pancholi_1 + 1 comment If K=2n then the loop will run twice and k will be set to 0. If k is a multiple of n then the array after k rotations will be same as initial array. k=k%n could also do the trick.

jarvian + 1 comment if k is a multiple of n then won't the remainder be 0?

jcacooper + 0 comments Yes. Which means, in effect, that no rotation should be performed upon the array, because rotating each element by k will have each of them end up right back where they started. Using 0 for k will have that effect.

luqmanalfarisi + 0 comments thank you sir.

jonathan_cheung1 + 1 comment This helped me out thanks

nijwm21 + 2 comments how it worked please can u explain me??

jonathan_cheung1 + 1 comment You can determine where in the array each element will end up with a simple calculation using the number of elements (n), the number of times you perform the operation (k), and an incrementing variable (use a for loop). Try to figure out the equation and use that answer as the array assignment. You need to use the while loop right before the array assignment because sometimes the calculation you perform will leave you with an array assignment value that is greater (hint) than the amount of array values so you just repeat the same equation until you get a valid value (something < n).

AhmadAliSabir + 0 comments (Y)

Dinesh1306 + 0 comments Here i have explained it in detail. Circular Array Rotation

AhmadAliSabir + 7 comments `int n,k,q,temp,m,z; cin>>n>>k>>q; int a[n]; for(int x=0;x<n;x++) { cin>>a[x]; } k=k%n; for(int y=0;y<k;y++) { temp = a[n-1]; for(int q=n-1;q>=1;q--) { a[q]=a[q-1]; } a[0]=temp; } for(int u=0;u<q;u++) { cin>>m; cout<<a[m]<<endl; }`

"Terminated due to timed out" on Case 5,12,13,14 ... help please .. Thanks !

rjdp3 + 1 comment I was using the nested loop algo, was getting timed out. Then i used this (JAVA) Collections.rotate(Arrays.asList(array_name), k);

i am a beginner, can anyone tell me is this a bad way to solve a problem, if yes why?

Stephen26 + 0 comments The Actual vision of the problem is to solve it by without actually making any rotations.because rotation takes more time and space.thats why you may get timeout errors if you try to solve it by rotations .we gotta have to solve it by doing calculations .Example: write a simple logic to determine what will be the output after k rotations.if K is equal to N then no rotations needed coz the array will be the same as original after rotations.

kumarnikhil104 + 0 comments hey ,,if u got the solution of your code please inform me also...thanxx;

Dinesh1306 + 1 comment No need to rotate the array you can do this problem much faster. Take a look here, i have explained it in detail. Circular Array Rotation

Hope it helped you

poonam2992 + 1 comment hi @Dinesh1306, I tried your solution, but I get this error when I try for large inputs as given in test cases: Sorry, we can't accept your submission. The custom input size should not exceed 50Kb.

Dinesh1306 + 1 comment hi @poon12, the solution is working fine, you must have done something wrong. Can you post your code here so that i can check.

poonam2992 + 0 comments hi @Dinesh1306 your solution got accepted. thanks :) but yes when i try the solution with large inputs, it gives me that custom input size error.

ashishgulati21 + 2 comments Same for me :/ someone please help

int main() { int n,k,q,r=0; cin >>n>>k>>q;

`int b[n]; int m[q]; for (int i=0;i<n;i++) { cin >> b[i]; } for (int i=0;i<q;i++) { cin >> m[i]; } for (int i=0;i<k;i++) { r=b[n-1]; for(int j=n-1;j>0;j--) { b[j]=b[j-1]; } b[0]=r; } for(int i=0;i<q;i++) { cout << b[m[i]]<<endl; } return 0;`

}

Dinesh1306 + 1 comment Check this

chikithapaleti99 + 0 comments int main() { long int n; long int k; long int q,i,t; scanf("%li %li %li", &n, &k, &q); long int a [n]; for (long int a_i = 0; a_i < n; a_i++) { scanf("%li",&a[a_i]); } long int *m = malloc(sizeof(long int) * q); for (long int m_i = 0; m_i < q; m_i++) { scanf("%li",&m[m_i]); } long int b[n]; for(i=0;i<n;i++){ t=i+k; t=t%n; b[t]=a[i]; } for (long int m_i = 0; m_i < q; m_i++) { printf("%ld\n",b[m[m_i]]); } return 0; }

chikithapaleti99 + 0 comments [deleted]

gozer_goose + 0 comments You can make another array and use modular arithematic approach to insert values in that array. In this way you will solve it in O(n) and there will be no timeout errors :D

teodora_vasilas + 0 comments i used this code insted of the second for:

rotate(a.begin(),a.end()-k,a.end());

polmki99 + 7 comments What's the space and time efficiency for this code?

n, k, m = map(int, input().strip().split()) arr = list(map(int, input().strip().split())) k %= n arr = arr[-k:] + arr[:-k] for i in range(m): print(arr[int(input().strip())])

hgnisrednivrug + 0 comments wow!!! fast and easy way to done the problem..

Pr0gr3550 + 0 comments [deleted]franchb1 + 0 comments Thank you!

Now I know

`%=`

amcavinue + 0 comments Really great solution!

nstoddar + 1 comment Thanks polmki99! Very clever implementation.

Here it is in Javascript for those interested.

function processData(input) { //Enter your code here var inputList = input.split('\n'); var details = inputList[0].split(" "); var arrayIdx = inputList.slice(2); var targetArray = inputList[1].split(" "); var k = details[1]%details[0]; targetArray = [].concat(targetArray.slice(-k),targetArray.slice(0,-k)); arrayIdx.map(function(elem){return console.log(targetArray[elem]);}); }

murnun + 1 comment Nice one liner using the built in functions! Unfortunately, this still fails when

`k`

is higher than`n`

(test case #4). You seem to be getting around it by overwriting`k`

with:`var k = details[1]%details[0];`

I'm curious to see if there are other, more algorithmic solutions to this in Javascript.

matt_heisig + 0 comments This works in Javascript for all test cases:

function main() { var n_temp = readLine().split(' '); var n = parseInt(n_temp[0]); var k = parseInt(n_temp[1]); var q = parseInt(n_temp[2]); a = readLine().split(' '); a = a.map(Number); for (var i=0; i<q; i++) { var m = readLine(); console.log(a.slice(m-k%n)[0]); } }

ryanlough + 0 comments [deleted]mail2karthk07 + 0 comments how about my solution is it good..

n,k,q = list(map(int, input().strip().split())) a = list(map(int, input().strip().split())) a = a[n-(k%n):]+a[0:n-(k%n)] [print(a[int(input())]) for _ in range(q)]

pooja1989mehta + 0 comments Wow! Lovely Solution.. But what if the direction of rotation is left?

I have given it a try, please let me know if I am wrong:

if(idx+rot <= arr.length) System.out.println(arr[idx+rot]); else System.out.println(arr[arr.length-(idx+rot)]);

Stephen26 + 1 comment no Rotation but still does the job :v CHECK THIS out c++ lovers

im noob in coding so i wrote it so big :(

`int b,n,k,q,ans=0; cin>>n>>k>>q; int a[n]; for(int i=0;i<n;i++) cin>>a[i]; if(k==n){ for(int i=0;i<q;i++) { cin>>b; cout<<a[b]<<endl; } } else if(k>n) { while(k>n) k=k-n; for(int i=0;i<q;i++) { ans=n-k; cin>>b; ans+=b; if(ans>n-1) ans-=n; cout<<a[ans]<<endl; } } else if(k<n) { for(int i=0;i<q;i++) { ans=n-k; cin>>b; ans+=b; if(ans> n-1) ans-=n; cout<<a[ans]<<endl; } } return 0;`

}

rajatchauhan + 0 comments smart one more way u could have actually stored rotated version of array while taking array input.

Sultan_of_Bits + 0 comments [deleted]Sultan_of_Bits + 1 comment Very elegant solution!

(\(\ (=':') (,(")(")

widefin + 0 comments bunny?

NikolaTECH + 0 comments [deleted]Dinesh1306 + 1 comment You can further reduce the time. No need to rotate the array just apply simple logic and you can do it in O(1) complexity per query. Check this solution Circular Array Rotation

bulicicnenad + 0 comments Query will be O(1) time complexity regardless of the implementation or correctness since you are accessing an indexed array. Your solution did not make accessing more efficient anymore than it is, but since you are inserting into an array in O(n) time and correctly accessing it passes all tests.

aravinthshc + 0 comments Thanks buddy!

aashirshukla + 1 comment How is that O(1) space? You're using an n element array.

Dinesh1306 + 1 comment It is O(1) per query. This problem can be solved without actually rotating the array.

Here is my solution Circular Array Rotation

aashirshukla + 1 comment Yeah, my bad. It's O(1) per query, but an O(n) space complexity algorithm in the end.

Dinesh1306 + 1 comment No,the algorithmn(which is the main part)is of O(1) time complexity you cannot optimize it any further. Space complexity is also optimized you cannot avoid using an array as the problem is based on it.

aashirshukla + 1 comment You cannot say that. And you cannot call it O(1),

For example if a problem asks us to sum up all numbers in an array, we can simply take an input and add it to a variable sum, or we can take all inputs in an array. What you just said implies that we cannot distinguish between these 2 algorithms, but we can(One is O(1), other is O(n).

Of course it isn't sensible to assume that we can solve this problem without the array in this particular case, but I still think that O(1) complexity is wrong.

Dinesh1306 + 1 comment Again you misunderstood what i am saying. I am saying that the algorithmn part(i.e. the if and else statment) is O(1) not the whole code, since in this problem we cannot run away from array. And i am claming that my solution is the most optimized one.

And BTW the example that you gave has O(n)time complexity not O(1) since for ever new element you are doing a computational opperation(i.e. adding the sum and the new input)

aashirshukla + 1 comment I'm talking about space complexity. The space complexity is not O(1), and the space complexities in my 2 examples were different(one is O(n) as we are using a WHOLE n element array, while in the other we're using one variable).

You on the other hand, are talking about the time complexity. It is O(1) per query and that's correct. But how is space in any way O(1) ? There exists an n element array.

Dinesh1306 + 1 comment Seems like we missunderstood each other. I was talking about time complexity the whole time. As for the space complexity yes it is O(n), O(1) is not possible in this problem since we have to store the elements.

vasukapil2196 + 1 comment hi bro,i am a beginner.How to understand these concepts of time complexity and space complexity.

Dinesh1306 + 1 comment You should not worry about these things if you are a beginner,but since you have asked i have explained it here, take a look. In the beginning your focus should be to complete the task without worrying about these time/space complexities.

poonam2992 + 1 comment thanku :)

Dinesh1306 + 0 comments My pleasure :)

mcihanozer + 0 comments Actually, you can do it in O(1) and O(1) space by simply using modulo.

ZEUS_DEVELOPER + 1 comment n,k,q=raw_input().split() n,k,q=[int(n),int(k),int(q)] s=raw_input() s=map(int,s.split()) while(q!=0): m=input() print s[(m-k)%n] q=q-1

# bitch plz python rules

morettocarlo + 1 comment I really like this one Zeus! I tried to make it more compact:

`n, k, q = map(int, input().strip().split()) a = [int(i) for i in input().strip().split(' ')] for i in range(q): m = int(input()) print(a[(m-k)%n])`

beckwithdylan + 0 comments and if you wanted to make it really compact..

n,k,q = list(map(int, input().split())) a = list(map(int, input().split())) print(*(a[(int(input())-k)%n] for _ in range(q)),sep='\n')

ZEUS_DEVELOPER + 1 comment n,k,q=raw_input().split() n,k,q=[int(n),int(k),int(q)] s=raw_input() s=map(int,s.split()) while(q!=0): m=input() print s[(m-k)%n] q=q-1

# bitch plz python rules

Codify_it + 0 comments Yeah, it does

`a,arr = [map(int,raw_input().split()) for _ in range(2)] for _ in range(a[2]): print (arr[-(a[1]%a[0]):] + arr[:-(a[1]%a[0])])[input()]`

wenditurner + 0 comments so good I could cry

cherrychen + 0 comments Wow!It is so effective compared to mine

samarth87 + 0 comments awsome

davinci_coder75 + 1 comment @piyush121 I would like to understand what you did with the modulo operation and how does rot help us in solving thiis code. I am beginner so please be patient and help me.

Dinesh1306 + 0 comments Visit here. I have explained it in detail.

tenzin392 + 0 comments I was faithfully doing a for loop for 1 rotation inside a dummy for loop to have k rotations. Then another for loop to output the m'th position. It worked, but O(n) became n*k; too long for 6 test cases. This comment inspired me to use modulus by n and only print the mth position numbers. I tried to understand it in my own way and shorten your code to:

System.out.println(a[(m-k+n)%n]);

ajeet_meena + 0 comments Could you please explain why time complexiety is O(N) instead of O(Q)?

harptheshark + 0 comments Hi piyush can you explain the math behind your solution that would be great

mpocatko + 0 comments This can be easily done with a one liner O(1) time and O(1) space

cout << a[(n+(m-k)%n)%n] << endl;

vcartera + 0 comments You don't need to use extra variable "rot". One can overwrite K with K%N if K is larger than N. Also, there is no need to call arr.length because you already have N.

octy40 + 1 comment This is pretty much more elegant than my solution of using a queue, but a question that I'm having is why use k%n? Can someone please explain this logic?

Tx

john_manuel_men1 + 0 comments Because when the number of rotations(k) equals the size of the array(n), the array returns to it's original setup. For example, after 3 rotations, this array is back to original:

[1,2,3] 0 original [3,1,2] 1 rotation [2,3,1] 2 rotations [1,2,3] 3 rotations //Back to original setup [3,1,2] 4 rotations // same as 1 rotation

Therefore if you have 4 rotations, then 4 % 3 is 1, so you will get the same result as if you only had 1 rotation to begin with.

xianmei_lei714 + 0 comments good catch on the k which can be bigger than the number of elements!!

thieugiatri4492 + 1 comment Can you guys explain to me this line

if(idx-rot>=0) System.out.println(arr[idx-rot]); else System.out.println(arr[idx-rot+arr.length]);

I don't understand why it can refer to the roation element of array?

JamesTre + 0 comments It's just because in the '(rot-1)th' elements of the array you will have negative indexes, causing errors or, even, segmentation error (as in test case 4). So, doing this, you add N to negative indexes to retrive the correct values from the former array, without rotating it at all.

http_o + 0 comments arr.unshift(arr.pop())

simran1707 + 1 comment Can anyone explain this easily from start ?

JamesTre + 2 comments Well, let's try explain using an example case:

If I have an array(a) with, let's say, N=5 elements: a0=0, a1=1, a2=2, a3=3 and a4=4.

Let's consider that I have to rotate this array K=6 times.So:

a0={0, 1, 2, 3, 4} (initial array)When I right-rotate 6 times this array, following the rules estipulated in this problem, I'll get this:

a1={4, 0, 1, 2, 3} (1st rotation)

a2={3, 4, 0, 1, 2} (2nd rotation)

a3={2, 3, 4, 0, 1} (3th rotation)

a4={1, 2, 3, 4, 0} (4th rotation)

a5={0, 1, 2, 3, 4} (5th rotation)

a6={4, 0, 1, 2, 3} (6th rotation)Observe that at the 5th rotation, we got the original array again (a5 == a0). In fact, at every N rotations we'll get the original array. So, we don't need to rotate the array K times if K is greater than N. We can just rotate it (K%N) times (rest of integer division, or just 'modulo operation'). In my example 6%5 = 1.

And, even in this case, I don't need to actually rotate the array, but just retrieve an element from the array whose position is 1 lower than it was in the original array.

WHAT???

Yes, let's consider the initial array and after 1 or 6 rotations, as follows:

a0={0, 1, 2, 3, 4}

a1={4, 0, 1, 2, 3} (1st and 6th rotation)If I try to retrieve the:

- 4th element, I'll get 3;

- 3rd element, I'll get 2, and so on.

Thus, if I subtract the number of rotations(K) from the index of the element, I'll get its value after K rotations, correct?

YES and NO!!!

a1[4] == a0[3]

a1[3] == a0[2]Hummm... aK[m] == a0[m-(k%N)]! Great. No rotation is necessary, but just a simple calculation...

Let's continue...a1[2] == a0[1]

a1[1] == a0[0]

a1[0] == a0[-1] OPS! There's no a[-1]!!!Here we get an error type "Index out of bounds". It's because we are trying to acces memory positions that are out of the array's boundaries. Probably, it is being used by another variable. A "Segmentation error" message may appear when K is much bigger than N (something like k=100000 and n=515, as in test case 4). It's because we are trying to acces memory positions that are out of the program boundaries and, probably, are being used by another application.

To correct these errors, we can use the same solution we used to simulate the K>N rotations: modulo operation!

The answer would be like this:

aK[m] == a0[(m+N-(K%N))%N].We add N to the index to assure it will never be negative.

Tricky, fast and easy.

Try implementing this in your application.I hope be helpful ;-)

thieugiatri4492 + 1 comment Sorry, but in this line

aK[m] == a0[(m+N-(K%N))

**%N**].you %N again after +N for what purpose? If i think correctly, it's for rotate again the m index?

shubamdadhwal + 0 comments That extra %N was added so that if our ans turns out to be greater than the number of elements in the array , the indexing should again start from index '0'. eg. for m=1, our the later formula without using %N will result to 5. but our ans should be equal to 0 and not 5 thats why we do modulus. so that it could become 0

shubamdadhwal + 0 comments Best Approach ever! Hats off!

Taylor40 + 0 comments Wow, its crazy to see how yours is so similar yet so different from my code. I instead placed the integer at the index it was going to be at from the very beginning

public static void main(String[] args) { Scanner in = new Scanner(System.in); int n = in.nextInt(); int cycles = in.nextInt(); int queries = in.nextInt(); int[] a = new int[n]; for(int a_i=0; a_i < n; a_i++){ a[(a_i+cycles) % n] = in.nextInt(); } for(int a0 = 0; a0 < queries; a0++){ int m = in.nextInt(); System.out.println(a[m]); } }

manek_sameer + 0 comments does it work in *

*4**th case?jpjaspreetmahal + 0 comments Can Someone Explain me Logic Behind it pls

marupatlapranay + 0 comments Thank you!!

priyagupta96 + 0 comments thanks man, its awesome. :)

ngtphu0905 + 0 comments i got "Segmentation Fault". Why?

gauravkochar_gk + 0 comments if (idx - rot >= 0) System.out.println(arr[idx - rot]); else System.out.println(arr[idx - rot + arr.length]); } will u plz make me understand ur logic?? how did it come to ur mind?

vsr625 + 0 comments It's O(1) time(for each query) and O(n) space, not the other way around.

Ishan81 + 0 comments Can somebody please explain the logic ? I did it with loop for shifting array elements but it shows timeout error for large testcases.

nguyenvanlinh_t1 + 0 comments Please explain for me why use a[(n-(k%n) +m) %n]?

ginni_nidhi + 0 comments can you please describe this to me:(a[(n - (k % n)+ m) % n])?

vishprajapati191 + 0 comments Just wanted to ask how do you came up with the one line solution to the problem.

System.out.println(a[(n - (k % n)+ m) % n]);

rohillakriti21 + 0 comments why do we have to use (k%n) instead of just k i.e. (n-k+m)? All TCs except for TC#4 succeed with k.

admiralciddu1 + 0 comments Whats the logic? Could you please explain it..

upendra28 + 0 comments why my code gives wrong answers ...?

vector <int> circularArrayRotation(vector <int> a, vector <int> m,int n,int k, int q) { while(k!=0) { int end=a[n-1]; for(int i=n-2;i>=0;i--) { a[i+1]=a[i]; } a[0]=end; k--; } return a; }

m999gs + 0 comments so, if you change the whole format of main method then how will it take the auto generated test cases?

red_shinrage + 0 comments what if the rotation was in left direction ?

anhtu91 + 0 comments Can you please explain, how did you find the solution?

Nathan3Fantom + 0 comments shouldnt you circulate the whole array instead of manipulating the indexes to find the answer.

rahulrajpl + 0 comments O(m) time and O(1) space.

def circularArrayRotation(a, k, queries): return [a[((len(a) - (k % len(a)))+q)%len(a)] for q in queries]

With Love, Python

kedarjog_vjti + 0 comments where are you rotating the array?

deeputhakurgbn + 0 comments u did amazing job...what i do...i cirular shift the whole array...can you suggest me the way...when you see a problem like this.

kn_neelalohitha + 0 comments Nice one!

Here is my code in C.#include <stdio.h> #include <stdlib.h> int main(){ int n,k,q; scanf("%d %d %d",&n,&k,&q); int a[100000],m,i = 0; while(i < n) scanf("%d",&a[(i++ + k) % n]); while(q--){ scanf("%d",&m); printf("%d\n",a[m]); } return 0; }

Position resulting because of rotation is computed first using

`((i++ + k) % n)`

.Then the array elements are stored in these positions in the*read*ing stage itself using`scanf()`

. Suggestions are welcome!nsh777 + 0 comments Why am I getting this error when I have not even touched main() ?

Here's my function code

`int i,j,arr[queries_count]; *result_count=queries_count; k = k % a_count; for(i=1;i<=queries_count;i++) { j=queries[i]-k; if(j<0) arr[i]=a[a_count+j]; else arr[i]=a[j]; } return arr;`

}

Segmentation Fault Error (stderr)

GDB trace: Reading symbols from solution...done. [New LWP 2592] Core was generated by `solution'. Program terminated with signal SIGSEGV, Segmentation fault.

# 0 fprintf (__fmt=0x400cc4 "%d", __stream=0x155d010)

`at /usr/include/x86_64-linux-gnu/bits/stdio2.h:97`

97 return __fprintf_chk (__stream, __USE_FORTIFY_LEVEL - 1, __fmt,

# 0 fprintf (__fmt=0x400cc4 "%d", __stream=0x155d010)

`at /usr/include/x86_64-linux-gnu/bits/stdio2.h:97`

# 1 main () at solution.c:97

PasanT + 0 comments Can anyone explain the maths behind this solution?

GizemN + 19 comments Here is another Java solution

`public static void main(String[] args) { Scanner in = new Scanner(System.in); int n, k ,q; n = in.nextInt(); k = in.nextInt(); q = in.nextInt(); int[] arr = new int[n]; for(int i=0; i<n; i++) { arr[(i+k)%n] = in.nextInt(); } for(int i=0; i<q; i++) { System.out.println(arr[in.nextInt()]); } }`

ucm_jwu + 1 comment can i just say...

your 'arr[(i+k)%n]' is GENIUS!

mad respect. thank you for thisss.

_silent_ + 1 comment how this arr[(i+k)%n]' works in the program

lhademmor + 1 comment It essentially does the 'rotations' before even assigning the array values in the first place, then uses modular arithmetics:

1) First, (i+k) ensures that each array value is 'moved' k positions to the right. Obviously, this means that towards the end of the array, values will exceed the array size, i+k > n-1, which we cannot allow to happen.

2) Then, by using %n ('mod n'), we ensure that whenever (i+k) exceeds the max array position (n-1), we loop back to position a[0] and continue from there. Essentially this works in the same was as a clock 'starts over' when the hands of the clock reach 12.

Modulo is a tricky mathematical concept, but once you understand how it's used here I think you will agree that this solution is absolutely

**BRILLIANT**. If you don't know what modulo is, there's a pretty good introduction here: https://www.khanacademy.org/computing/computer-science/cryptography/modarithmetic/a/what-is-modular-arithmeticsmithosagie24 + 0 comments Thanks. We need more people like you that take time to explain logic.

shauntrick + 0 comments Very creative solution ! I did it with deque but this is awesome ,It helped me to learn a lot !

manasb26 + 0 comments Simply awesome....

adityanovandri + 0 comments Awesome math

AshishSinha5 + 0 comments one of most creative solution i have ever seen for this type of problem......a complete genius

shaikhriyaz434 + 1 comment you are a genius brother....

GizemN + 0 comments Thank you that is very kind of you but I would rather not to be called brother as I am a female programmer. :)

spal02482 + 0 comments The brilliant way of using modulo-aruthmetic...

georgecartridge + 1 comment Could you possibly explain, or point to another resource, where I can better understand what is going on with

`(i+k)%n`

GizemN + 0 comments The element at the i th position moves right k times: (i+k)

When we reach the last index of the array we need to go back to first index and that is what we are doing with %n.

You can have a better understanding by appliying the algorithm on the sample input.

shubhamkanwal + 0 comments Bravo!

Annanya + 0 comments genius.

bleahy + 0 comments This is so elegant! Thank you!

msputtam + 0 comments Awesome math here !!!!!.

I did this in another way..but achived 17.33 pts only..

hamza_elouakili + 0 comments Genius

_silent_ + 0 comments can you explain me how this code works?

harshalkothawad1 + 0 comments Great solution!!!!!

lhademmor + 0 comments It took me well over an hour of intense thinking and googling of modular arithmetics, but I finally understood this solution, and I have to agree with the rest of the commenters: it's absolutely beautiful in its simplicity

muditanimje6 + 0 comments smart solution !!

bksingh + 0 comments Very nicely done, vote up :)

namit2saxena + 0 comments That's a genius solution. wow! How are you guys able to think this far? What books do you guys follow?

edmondsk64 + 0 comments I can't believe this is just a warm up exercise... i should pratice more

JetFault + 1 comment JS Math solution

function processData(input) { var lines = input.split('\n'); var arr = lines[1].split(' '), rot = lines[0].split(' ')[1], n = arr.length; for (var i = 2; i < lines.length; i++) { var m = lines[i], oldM = (n + (m - (rot % n))) % n console.log(arr[oldM]); } }

ooade + 0 comments Cmon! What were you thinking to arrive at this? Awesome Math!

oldM = (n + (m - (rot % n))) % n

FAKRUDEEN + 0 comments one liner without any loop

cout<<a[(n-(k%n)+m)%n]<<endl;

aseefm25 + 2 comments can anyone please tell that what is teminated due to timeout

#include <math.h> #include <stdio.h> #include <string.h> #include <stdlib.h> #include <assert.h> #include <limits.h> #include <stdbool.h> int main(){ int n,k,q,temp,i,j,a[100000],b[500]; scanf("%d %d %d",&n,&k,&q); for(i=0;i<n;i++){ scanf("%d",&a[i]); } for(j=0;j<k;j++) { temp=a[n-1]; for(i=n-1;i>0;i--) a[i]=a[i-1]; a[0]=temp; } for(i=0;i<q;i++) scanf("%d",&b[i]); for(i=0;i<q;i++) printf("%d\n",a[b[i]]); return 0; }

vishalxviii + 0 comments same problem and same code bro

azheruddin617mr1 + 0 comments its taking too much time for larg inputs...

hvogue + 2 comments We don't need to actually rotate the array. We can just use basic math to pull the entry from the original array:

`int shift = n - (k % n); int index = (shift + m ) % n;`

devvrat_arya + 0 comments Clever..

D4RIO + 1 comment What a powerful and flexible language Perl

chomp(($n, $k, $q)=split(/ /,<>)); chomp(my @A=split(/ /,<>)); while(<>){ print $A[($_-$k)%$n],"\n"; }

vasilij_kolomie1 + 0 comments really better Python:

def circularArrayRotation(a, k, queries):

a = a[-k:] + a[:-k]

return [a[i] for i in queries]

jhorar007 + 5 comments i am getting time out error in some of test cases ..any help??

abhiranjan + 0 comments Please refer to editorial.

jayantsingh3041 + 0 comments N & K both <=10^5 remember

Indrasen + 0 comments Remember k=k%n

Gautham_B_A + 2 comments Do not do any rotation. This problem requires you to handle it through simple calculation. You need to compute what the resulting index turns out to be after rotation.

alegionofgenius + 0 comments Thanks man, your comment was key in helping me get what this was all about....

bhavini + 0 comments Algorithm to shift each element of array by one position.

1. Store first element of input Arrays in C in a temporary variables in C(temp = inputArray[0]).

2. Starting from inputArray[1], shift all positions to left adjacent index(inputArray[i-1] = inputArray[i]).

3. Store temp value at last index of inputArray(inputArray[N-1] = temp).

**Time Complexity**: O(n)

**Space Complexity**: O(1)

Source : Array rotation by shifting elements

Here is the algorithm to rotate an array c program

maximshen + 0 comments As other ppl suggested, just focus on math, no extra space complexity needed, no loop needed, simplest solution is linear. Write yourself some example, what if K is greater than N, what if K is less than N, etc

Sort 1327 Discussions, By:

Please Login in order to post a comment