### In this post i will explain the Circular array rotation problem in the most efficient way. Here is the problem statement taken directly from hackerrank.com.

Here is the trick. We will consider 2 cases, 1st is when k<m and 2nd is when k>m, you will get to know why we are considering these two cases as we go on.

- Let the input parameters be n, k=4 and m=5, so the numbers would be (1,2,3,4,5,6,7,8,9...n-1,n) keep note of the number at index m-k (i.e. at index 1). Now after k=4 rotations the resulting numbers will be (n-3,n-2,n-1,n,1,2,3,4 ...n-5,n-4). Note that the current number at index m=5(which in this case is 2) was at an index 1 (i.e. at
**m-k**). So we can directly find the element at index m=5 without actually rotating the array by outputting the element at index (**m-k**). - Now let k=4 and m=3. In this case the number that is at index m=3 was actually at an index (
**n-k+m**). Here also we can find the element at m=3 without rotating the array by outputting the element at index (**n-k+m**).

**k>n**well we can tackle that by using the mod(%) operator.For those of you who do not know how mod(%) operator works. Basically it returns the remainder, let

**k=r%n**, so if rotation(i.e.

**r**) is greater than

**n**, due to the mod(%) operator the value of

**k**will be remainder of

**r/n**. e.x. if r=9, n=6 than k=3 and if

**r**is multiple of

**n**i.e. if r=5,10,15,20..... and n=5 than k=0 after the operation.

Here is my code.

#include <iostream>

using namespace std;

int main() {

int n,k,q,m,j;

cin>>n>>k>>q;

k%=n;/* Or k=k%n which will make sure that the rotation is in circular manner. The mod(%) operator returns the remainder so if rotation(i.e. k) is greater than n, due to the mod(%) operator the value of k will be remainder of k/n. e.x. if k=9, n=6 than k=3 after this operation and if k is multiple of n i.e. if k=5,10,15,20..... and n=5 than k=0 after the operation. */

int *A= new int[n]/* OR int A[n] ---initializing an array A of size n . To know more about the format and it's use search fordynamic array*/

for(int i=0;i<n;i++)cin>>A[i];/* filling the array */

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

cin>>m;/* taking the index */

j=m-k;

if(j<0) cout<<A[n+j]<<endl;/* the case when k>m. The output is A[n+j]which is nothing but A[n+m-k]. */

else cout<<A[j]<<endl;/* the case when k<m. The output is A[j] which is nothing but A[m-k]. */

}

return 0;

};

*******IF YOU WANT ME TO EXPLAIN A PERTICULAR PROBLEM THAN PLEASE LEAVE A LINK TO THE PROBLEM IN THE COMMENT*******

_{}

^{}

very clear explanation, thank you so much...

ReplyDeleteMy pleasure :)

Delete#include

Delete#include

int main(){

long int n;

long int k,l;

long int *a,*b,a_i;

scanf("%ld %ld %ld",&n,&k,&l);

a = (long int*)malloc(n * sizeof(int));

b = (long int*)malloc(l * sizeof(int));

for( a_i = 0; a_i < n; a_i++){

scanf("%ld",&a[((k+a_i)% n)]);

}

for(a_i=0;a_i<l;a_i++){

scanf("%ld",&b[(a_i)]);

}

for( a_i = 0; a_i < l; a_i++){

printf("%ld\n",a[ b[a_i] ]);

}

return 0;

}

whats wrong with my code , i don't understand it only satisfies single case

ReplyDeleteint main(){

int n;

int k;

int q;

int j;

cin >> n >> k >> q;

vector a(n);

for(int a_i = 0;a_i < n;a_i++){

cin >> a[a_i];

}

j = k%n;

for(int a0 = 0; a0 < q; a0++){

int m;

cin >> m;

if((m-j)<0)

cout << a[m-j+n];

else

cout << a[m-j]<<endl;

if(a0+1 < q)

cout << endl;

}

return 0;

}

Can you tell me what is wrong my logic? Except for the sample test and test case 15, all the others fail. It is really bugging me now. Any insight would be greatly helpful! Thanks

Hi!!

DeleteThis is the mistakes in your code.

1. In the part "cout << a[m-j] << endl;" in the else statement. It should be "cout<<a[m-j];" .That "endl" is not needed since and hence it is causing error .

"if(a0+1 < q)

cout << endl;"

is already taking care of it.

***Some advice***

1. While writing the code try to optimize it. Check that you are not doubling any calculation. E.g. in your code you are doubling this "(m-j)" calculating operation. Instead you could have just used an extra variable as say "z=m-z ". It is not that significant but still it's a good practice.

Note that there are various ways to optimize a code, not computing something multiple times is one of them.

2. This part of your code

"if(a0+1 < q)

cout << endl;"

is not necessary. You are making the processor do some extra work of comparing " a0+1 and q " each time. Instead you could have just put an "endl" in the if else statement like this

"if((m-j)<0)

cout << a[m-j+n]<<endl;

else

cout << a[m-j]<<endl;".

Hope it helped you :)

wow, thanks a lot this has really helped me to understand circular arrays.

ReplyDeleteGlad it helped you :)

DeleteAlso I am planing to put a tutorial for you guys so keep checking this blog. This tutorial will not be like any reference book instead i will explain the topics the way i understood it, so that you will be able to grasp it much easily.

I am not able to understand the case where m<k.when k=4 and m=3 , the element at index m=3 is n, which was at n before rotation.

ReplyDeleteI am not able to understand the case where m<k.when k=4 and m=3 , the element at index m=3 is n, which was at n before rotation.

ReplyDeleteThe index of n was n-1( which is nothing but n-k+m for k=4 and m=3) since in array the index starts from 0 and goes till n-1.

Deleteint n = in.nextInt();

ReplyDeleteint k = in.nextInt();

int q = in.nextInt();

int[] a = new int[n];

int[]b=new int[n];

for(int a_i=0; a_i < n; a_i++){

a[a_i] = in.nextInt();

}

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

{

b[0]=a[n-1];

for(int i=0;i<n-1;i++)

{

b[i+1]=a[i];

}

a=b.clone();

}

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

{

int m=in.nextInt();

System.out.println(a[m]);

}

WHY DOESNT THIS WORK FOR SOME TEST CASES?

for k>m I used the logic m = (k + m - 1)%n. but i get errors. can u point out my mistake? thank u.

ReplyDeleteSorry for the late reply. Can you please post your code since i don't know what you have written in your "cout" after applying your logic.

DeleteExcellent Dinesh!

ReplyDeleteThanks e-M@x :)

DeleteThank! Great explanation :)

ReplyDeleteNew Year 2017 Wallpapers

ReplyDeleteBrilliant...!!! Worked like a charm... :)

ReplyDeleteint main(){

ReplyDeleteint n,j;

int k;

int q;

int a[n];

scanf("%d %d %d",&n,&k,&q);

k%=n;

for(int i=0;i<n;i++){

scanf("%d",&a[i]);

}

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

int m;

scanf("%d",&m);

j=m-k;

if(j<0)

printf("%d",a[n+j]);

else

printf("%d",a[j]);

}

return 0;

}

it shows segmentation fault..!!tell me problem.

help me..

Hi!!

DeleteI didn't find anything which should give segmentation fault error.It ran fine without any error when i tried running it.Although you have done a minor mistake, which is

The printf in the if-else statement should contain "/n" so that every output is in the next line.

int main(){

ReplyDeleteint n;

int k;

int q;

scanf("%d %d %d",&n,&k,&q);

int a[10];

for(int a_i = 0; a_i < n; a_i++){

scanf("%d",&a[a_i]);

}

for(int a0 = 0; a0 < q; a0++){

int m,j;

scanf("%d",&m);

j=m-k;

if(j<0) printf("%d\n",a[n+j]);

else printf("%d\n",a[j]);

}

return 0;

}

compilation is successful but it gives segmentation fault after submission.Please find error...

help me

int main(){

ReplyDeleteint n;

int k;

int q;

scanf("%d %d %d",&n,&k,&q);

int *a=(int*)malloc(sizeof(int)*n);

for(int a_i = 0; a_i < n; a_i++){

scanf("%d",&a[a_i]);

}

for(int a0 = 0; a0 < q; a0++){

int m;

scanf("%d",&m);

if((m-k)<0) printf("%d\n",a[n+m-k]);

else printf("%d\n",a[m-k]);

}

return 0;

}

segmentation fault is only in test case 4 and other case is perfect.

just write a statement " k=k%n"

Deleteafter assigning the values of k and n

sry..im a beginner in coding can u tell me why should we add k=k%n statement...can u plss explain me clearly

DeleteHi Bhakyalashmi!!

DeleteIf the statement k=k%n is not there than for a large value of "k" let's say k=100 and small value of "n", let's say, n=10. As "m" has to be less than or equal to "n"(since it is the index) so let's take it as 10, than the statement "cout<<a[n+m-k] "

OR "cout<<a[m-k]"

will give error because the size of our array is "n" (which is less than "n+m-k" or "m-k" in our example) , since we are trying to access an index which is not there.

Hope it helped you :)

Awesome explanation and elegant solution. Thanks!

ReplyDeleteBtw, do you have similar challenges. I am a newbie to C and very bad at algorithms. I want to learn more!

excellent solution ...like a pro..

ReplyDeletebut how did you get this idea ...

#include

ReplyDeleteusing namespace std;

int main ()

{

long int n,k,q,m;

cin>>n>>k>>q;

long int arr[n];

for(long int i=0;i>arr[i];

}

while(q--)

{

cin>>m;

long int pos=m;

if(k%n==0)

pos=(pos+k)%n;

else

pos=(pos+k-1)%n;

cout<<arr[pos]<<endl;

}

}

whats wrong in the code?

Why am I getting this error when I have not even touched main() ?

ReplyDeleteHere'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

I know it is very much late. Sorry for that. But I got error of time out. even I ran my code in code blocks IDE it does't respond. and from all test cases only 6 problems are not accepting solution and giving error. I have input of that cases also. If you can Help me pls help. I am beginner and just joined collage. It will very kind of you if you help me sir. I am posting my code below.

ReplyDeleteCODE:

#include

using namespace std;

int main()

{

long long int i,j,u,n,k,m,p;

cin>>n;

cin>>k;

cin>>m;

long long int a[n],b[m];

for(i=0;i>a[i];

}

for(i=0;i>b[i];

}

k=k%n;

for(u=0;u=0;j--)

{

a[j]=a[j-1];

}

a[0]=p;

}

for(i=0;i<m;i++)

{

cout<<a[b[i]]<<endl;

}

}

If you want test case input I will post that also