We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.

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!

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...

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!👍

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

#include<cmath>#include<cstdio>#include<vector>#include<iostream>#include<algorithm>usingnamespacestd;intmain(){/* Enter your code here. Read input from STDIN. Print output to STDOUT */intn,k,q,i,s=0,e=0,t=0,b;cin>>n>>k>>q;inta[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;}return0;}

#include<iostream>#include<vector>#include<algorithm>#include<iterator>intmain(){intn;std::cin>>n;// array sizeintk;std::cin>>k;//no of rotationsintq;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--){intindex;std::cin>>index;std::cout<<vec[index]<<std::endl;}return0;}

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]);
}
}

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.

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.

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.

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.

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;👍

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.

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;
}

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.

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.

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.

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).

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.

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.

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

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.

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

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.

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.

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.

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)

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.

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.

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.

@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.

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:

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.

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?

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]0original[3,1,2]1rotation[2,3,1]2rotations[1,2,3]3rotations//Back to original setup[3,1,2]4rotations// 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.

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.

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...

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.

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

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

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?

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!

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.

// Complete the circularArrayRotation function below.
static int[] circularArrayRotation(int[] a, int k, int[] queries) {
int last=a[a.length-1];
for(int i=a.length-2;i>=0;i--)
{
a[i+1]=a[i];
}
a[0]=a[last];
for(int i=0;i<queries.length;i++)
{
int c=queries[i];
int m=a[c];
return m;
break;
}
}
private static final Scanner scanner = new Scanner(System.in);
public static void main(String[] args) throws IOException {
BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));
String[] nkq = scanner.nextLine().split(" ");
int n = Integer.parseInt(nkq[0]);
int k = Integer.parseInt(nkq[1]);
int q = Integer.parseInt(nkq[2]);
int[] a = new int[n];
String[] aItems = scanner.nextLine().split(" ");
scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");
for (int i = 0; i < n; i++) {
int aItem = Integer.parseInt(aItems[i]);
a[i] = aItem;
}
int[] queries = new int[q];
for (int i = 0; i < q; i++) {
int queriesItem = scanner.nextInt();
scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");
queries[i] = queriesItem;
}
int[] result = circularArrayRotation(a, k, queries);
for (int i = 0; i < result.length; i++) {
bufferedWriter.write(String.valueOf(result[i]));
if (i != result.length - 1) {
bufferedWriter.write("\n");
}
}
bufferedWriter.newLine();
bufferedWriter.close();
scanner.close();
}

hi @1634810124_coe3b
you have not used the k variable and also you have wrote a[0]=a[last]; do not assign like this ..because you are using a[0] in the loop afterwards.
Tip-->Assign the values in a[0] using temporary variable.
since you are using 2 for loops and probably you need one while loop or nested for loop for this kind of approach ...so you may face timeout in some testcases.
good luck

## Circular Array Rotation

You are viewing a single comment's thread. Return to all comments →

Easy and fast as hell --> O(n) time and O(1) Space........

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!I did something similar, but I used mod in case

K > arr.lenth + idx.

same here. I know it's too late to reply :P

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

In your solution, you could use another modular arithmetic, to ensure the index stays within the boundaries of the array.

In my solution the index are within the boundaries.

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

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

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...

Dude please fix your "include"s they seem ugly :)

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!👍

why my code gives wrong answers ...?

you need to return q not a.

you are not supposed to print the whole array a but only the elements at positions in queries

how come!, It's not working???

if you try to interchange the value,t then it does not work,

if(j+1!=n-1)

in your code there is assignment of values....shifting of values is absent..

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

your code is wrong due to elae statement

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

Thank you very much..passed all test cases.

it will work

simpler one:

why are you taking modulus of k???

refer to my code

refer this

same to you. but if you dry run the code ,then can you understand what is wrong with the code !!

it is failing for one case when modulo is used, any help?

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.

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 {

}

Same problem in another solution.

Try this solution it will work

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.

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.

yes, thats what the problem is , i m not understanding why is it not accepting the solution.

Anyways, Thanks for the help

Do this. Had same issue and it fixed it.

k=k%n; Looking at the test case found that k is pretty large.

thank you

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

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

Thank you

i got runtime error by using this

same problem

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.

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 ?

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

## 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<

}

problem : Terminated due to time out??

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.

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;👍

Helpful!!

you figured out the time problem bro!!!! great

Thanks!!

i tried the same thing but the test case #4 is showing runtime error

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.

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.

Thanks :)

Thanks!

Thanks!!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.

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:

what if array size is 3 and it is rotated 4 times basically n=3 and k=4 and I want value at index = 0

That is the same as if the array was rotated once. So, at index 0 we'll find the element formerly located at index 1. peace of cake..

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

Python solution using mod:

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)])

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

Another simple python solution

what is the faster?

or we can simply do like this by using python collections

hi @vasilij_kolomie1 your code doesn't work for test case 4

Yes when the number of rotations is too big you need to use use rotations mod number of prisoners

Can you please explain your solution ? why are you taking mod here ?

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

Oh!So that is what it is!I got it!Thanks!

And this idea will reduce the time ,right?

Java mod solution:

Failed for one test case.

Test case 4? Segmentation fault?

Yes

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.

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.

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.

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

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.

thank you sir.

This helped me out thanks

how it worked please can u explain me??

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).

(Y)

Here i have explained it in detail. Circular Array Rotation

Thanks, It worked in Python. In fact, it would work in any language.

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

try to solve in O(n).

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?

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.

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

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

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.

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

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.

Same for me :/ someone please help

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

}

Check this

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

i used this code insted of the second for:

What's the space and time efficiency for this code?

wow!!! fast and easy way to done the problem..

Thank you!

Now I know

`%=`

Really great solution!

Thanks polmki99! Very clever implementation.

Here it is in Javascript for those interested.

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:I'm curious to see if there are other, more algorithmic solutions to this in Javascript.

This works in Javascript for all test cases:

when i ran my code only sample test cleared and rest failed

found out what the problem was, new JS code:

Hi, could you please explain what is happening here? Thanks

how about my solution is it good..

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)]);

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

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

}

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

Very elegant solution!

bunny?

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

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.

Thanks buddy!

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

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

Here is my solution Circular Array Rotation

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

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.

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.

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)

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.

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.

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

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.

thanku :)

My pleasure :)

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

## bitch plz python rules

I really like this one Zeus! I tried to make it more compact:

and if you wanted to make it really compact..

## bitch plz python rules

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()]`

so good I could cry

Wow!It is so effective compared to mine

awsome

@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.

Visit here. I have explained it in detail.

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:

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

Hi piyush can you explain the math behind your solution that would be great

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

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

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.

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

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:

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.

good catch on the k which can be bigger than the number of elements!!

Can you guys explain to me this line

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

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.

arr.unshift(arr.pop())

Can anyone explain this easily from start ?

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 ;-)

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?

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

Best Approach ever! Hats off!

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

does it work in *

4*th case?Can Someone Explain me Logic Behind it pls

Thank you!!

thanks man, its awesome. :)

i got "Segmentation Fault". Why?

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?

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

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

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

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

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

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.

Whats the logic? Could you please explain it..

why my code gives wrong answers ...?

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

what if the rotation was in left direction ?

Can you please explain, how did you find the solution?

shouldnt you circulate the whole array instead of manipulating the indexes to find the answer.

O(m) time and O(1) space.

With Love, Python

where are you rotating the array?

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.

Nice one!

Here is my code in C.

Position resulting because of rotation is computed first using

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

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

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

Here's my function code

}

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)

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

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

## 1 main () at solution.c:97

Can anyone explain the maths behind this solution?

python 3 https://www.hackerrank.com/challenges/circular-array-rotation/forum/comments/514048

sir can you please help me.Whats wrong with my code ??

import java.io.

; import java.math.; import java.security.; import java.text.; import java.util.; import java.util.concurrent.; import java.util.regex.*;public class Solution {

}

hi @1634810124_coe3b you have not used the k variable and also you have wrote a[0]=a[last]; do not assign like this ..because you are using a[0] in the loop afterwards. Tip-->Assign the values in a[0] using temporary variable. since you are using 2 for loops and probably you need one while loop or nested for loop for this kind of approach ...so you may face timeout in some testcases. good luck

It's for C (''Godspeed!")

what this line is doing "arr[i] = in.nextInt();"

Wow. The core of the solution is two lines in Ruby (or one line if you don't mind calling a.length three times).

It may be possible to simplify my expression, but I wasn't able to see how to reduce it.

gr8 plz send your all the solutions in the discussion section thnks bro

why is it saying subscripted value is not an array,vector or pointer...

Thanks

Nice solution.. Need to By heart this formula..