piyush121 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
modbased 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 I did something similar, but I used mod in case
K > arr.lenth + idx.
ZEUS_DEVELOPER [deleted]
scorpionk same here. I know it's too late to reply :P
chikithapaleti99 [deleted]
Free_Electron [deleted]
c650Alpha Ah. I was doing some weird modular arithmetic, which led to funky outcomes for the unknown test cases.
Dinesh1306 [deleted]
roman_balzer 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 In my solution the index are within the boundaries.
rn27in 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 #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 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 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 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 you need to return q not a.
mykz950 if(j+1!=n-1)
Saurav_Gaikwad1 in your code there is assignment of values....shifting of values is absent..
S_A_G hi Change your condition as a[j-1]=a[j]; and j=n-1;j>=0;j-- in for loop
vikram777 your code is wrong due to elae statement
kusaalpokharel 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 #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 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 #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 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 refer to my code
rvrishav7 #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 it is failing for one case when modulo is used, any help?
Dinesh1306 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 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 Same problem in another solution.
Dinesh1306 Try this solution it will work
piyushb9 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 [deleted]Dinesh1306 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 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 Add one line k=k%n; before second loop start then you'll pass all the test.
bpalaciosa Thank you
vedesh_vedu1 i got runtime error by using this
Vikramhunter same problem
JamesTre 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 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 I posted my code, if u could look at it in the comment section above that would be great!
ankur8090889931 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 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 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 Helpful!!
myselfshailander you figured out the time problem bro!!!! great
jsbzwork Thanks!!
aayushrangwala i tried the same thing but the test case #4 is showing runtime error
danutzp 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 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 Thanks :)
malkandmms Thanks!
__PinkMan Thanks!!
JamesTre 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 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 [deleted]
rkarthik3cse Thank you.
Dinesh1306 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 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 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 @hasan2020mainul can you explain the operation a(m-k)%len(a) you did?
vacky11 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 what is the faster?
def circularArrayRotation(a, k, queries):
a = a[-k:] + a[:-k]
return [a[i] for i in queries]
rwan7727 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 Can you please explain your solution ? why are you taking mod here ?
Hiren_Italiya he's doing mod caz after n rotation all elements will come at same position as starting point.
HuangZhenyang Oh!So that is what it is!I got it!Thanks!
HuangZhenyang And this idea will reduce the time ,right?
guitarman Java mod solution:
for(int i = 0; i < numQueries; i++) { System.out.println(array[(arraySize + (in.nextInt() - (numRotations % arraySize))) % arraySize]); }
karthik1301 Failed for one test case.
anuj_pancholi_1 Test case 4? Segmentation fault?
karthik1301 Yes
anuj_pancholi_1 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 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 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.
luqmanalfarisi thank you sir.
jonathan_cheung1 This helped me out thanks
nijwm21 how it worked please can u explain me??
jonathan_cheung1 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 (Y)
Dinesh1306 Here i have explained it in detail. Circular Array Rotation
AhmadAliSabir 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 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 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 hey ,,if u got the solution of your code please inform me also...thanxx;
Dinesh1306 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 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 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 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 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 Check this
chikithapaleti99 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 [deleted]
gozer_goose 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 i used this code insted of the second for:
rotate(a.begin(),a.end()-k,a.end());
polmki99 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 wow!!! fast and easy way to done the problem..
Pr0gr3550 [deleted]
franchb1 Thank you!
Now I know
%=
amcavinue Really great solution!
nstoddar 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 Nice one liner using the built in functions! Unfortunately, this still fails when
kis higher thann(test case #4). You seem to be getting around it by overwritingkwith:var k = details[1]%details[0];I'm curious to see if there are other, more algorithmic solutions to this in Javascript.
matt_heisig 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 [deleted]mail2karthk07 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 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 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 smart one more way u could have actually stored rotated version of array while taking array input.
Sultan_of_Bits [deleted]Sultan_of_Bits Very elegant solution!
(\(\ (=':') (,(")(")
widefin bunny?
NikolaTECH [deleted]Dinesh1306 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 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 Thanks buddy!
aashirshukla How is that O(1) space? You're using an n element array.
Dinesh1306 It is O(1) per query. This problem can be solved without actually rotating the array.
Here is my solution Circular Array Rotation
aashirshukla Yeah, my bad. It's O(1) per query, but an O(n) space complexity algorithm in the end.
Dinesh1306 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 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 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 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 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 hi bro,i am a beginner.How to understand these concepts of time complexity and space complexity.
Dinesh1306 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 thanku :)
Dinesh1306 My pleasure :)
mcihanozer Actually, you can do it in O(1) and O(1) space by simply using modulo.
ZEUS_DEVELOPER 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 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 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 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 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 so good I could cry
cherrychen Wow!It is so effective compared to mine
samarth87 awsome
davinci_coder75 @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 Visit here. I have explained it in detail.
tenzin392 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 Could you please explain why time complexiety is O(N) instead of O(Q)?
harptheshark Hi piyush can you explain the math behind your solution that would be great
mpocatko 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 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 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 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 good catch on the k which can be bigger than the number of elements!!
thieugiatri4492 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 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 arr.unshift(arr.pop())
simran1707 Can anyone explain this easily from start ?
JamesTre 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 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 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 Best Approach ever! Hats off!
Taylor40 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 does it work in *4*th case?
jpjaspreetmahal Can Someone Explain me Logic Behind it pls
marupatlapranay Thank you!!
priyagupta96 thanks man, its awesome. :)
ngtphu0905 i got "Segmentation Fault". Why?
gauravkochar_gk 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 It's O(1) time(for each query) and O(n) space, not the other way around.
Ishan81 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 Please explain for me why use a[(n-(k%n) +m) %n]?
ginni_nidhi can you please describe this to me:(a[(n - (k % n)+ m) % n])?
vishprajapati191 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 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 Whats the logic? Could you please explain it..
upendra28 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 so, if you change the whole format of main method then how will it take the auto generated test cases?
red_shinrage what if the rotation was in left direction ?
anhtu91 Can you please explain, how did you find the solution?
Nathan3Fantom shouldnt you circulate the whole array instead of manipulating the indexes to find the answer.
rahulrajpl 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 where are you rotating the array?
deeputhakurgbn 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 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 usingscanf(). Suggestions are welcome!
nsh777 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:9797 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:971 main () at solution.c:97
PasanT Can anyone explain the maths behind this solution?
GizemN 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 can i just say...
your 'arr[(i+k)%n]' is GENIUS!
mad respect. thank you for thisss.
_silent_ how this arr[(i+k)%n]' works in the program
lhademmor 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-arithmetic
smithosagie24 Thanks. We need more people like you that take time to explain logic.
shauntrick Very creative solution ! I did it with deque but this is awesome ,It helped me to learn a lot !
manasb26 Simply awesome....
adityanovandri Awesome math
AshishSinha5 one of most creative solution i have ever seen for this type of problem......a complete genius
shaikhriyaz434 you are a genius brother....
GizemN Thank you that is very kind of you but I would rather not to be called brother as I am a female programmer. :)
spal02482 The brilliant way of using modulo-aruthmetic...
georgecartridge Could you possibly explain, or point to another resource, where I can better understand what is going on with
(i+k)%nGizemN 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 Bravo!
Annanya genius.
bleahy This is so elegant! Thank you!
msputtam Awesome math here !!!!!.
I did this in another way..but achived 17.33 pts only..
hamza_elouakili Genius
_silent_ can you explain me how this code works?
harshalkothawad1 Great solution!!!!!
lhademmor 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 smart solution !!
bksingh Very nicely done, vote up :)
namit2saxena That's a genius solution. wow! How are you guys able to think this far? What books do you guys follow?
edmondsk64 I can't believe this is just a warm up exercise... i should pratice more
JetFault 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 Cmon! What were you thinking to arrive at this? Awesome Math!
oldM = (n + (m - (rot % n))) % n
FAKRUDEEN one liner without any loop
cout<<a[(n-(k%n)+m)%n]<<endl;
aseefm25 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 same problem and same code bro
azheruddin617mr1 its taking too much time for larg inputs...
hvogue 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 Clever..
D4RIO What a powerful and flexible language Perl
chomp(($n, $k, $q)=split(/ /,<>)); chomp(my @A=split(/ /,<>)); while(<>){ print $A[($_-$k)%$n],"\n"; }
vasilij_kolomie1 really better Python:
def circularArrayRotation(a, k, queries):
a = a[-k:] + a[:-k]
return [a[i] for i in queries]
jhorar007 i am getting time out error in some of test cases ..any help??
abhiranjan Please refer to editorial.
jayantsingh3041 N & K both <=10^5 remember
Indrasen Remember k=k%n
Gautham_B_A 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 Thanks man, your comment was key in helping me get what this was all about....
bhavini 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 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