Array Rotation

help
1

Hi,

The practice problem I have been working on - COF1MED1 Problem - CodeChef

The solution which I had submitted-
https://www.codechef.com/viewsolution/44066530

Can anyone tell whether my logic is incorrect or is there any other problem.
Help would be appreciated.

Thanks

2

Hey
I tried this problem in C. The code worked fine on my compiler, but the submission was still marked wrong. Even I am unable to understand where the problem is.
PS- I am a rookie to CodeChef and coding itself. :sweat_smile:

3

Why is the code so complex. That’s not the way someone actually solves the problem.
Here is my approach (and so, everyone’s).

  • Let ind be pointing to 0 initially.
  • Now process queries.
  • If the query is to rotate the array left by d units, then set ind to (ind + d) % n.
  • If the query is to rotate the array right by d units, then set ind to (ind + n - d) % n.
  • If the query is to find the element at index d, then simply output a[(ind + d - 1) % n].

I hope there is no need for further explanation. I am pretty much sure this works.

4

Why are there no Accepted solutions :scream:?
Surprisingly, both of my solutions (C and Python, implementing the above approach) gave WA. There is no editorial for the problem :thinking:

5

Your solution is pretty neat.

My approach is I am actually rotating the array for every query.

1 Like
6

Don’t know.
I tried giving inputs for my code, it worked.
I thought it was failing some hidden test case, so I asked here.

1 Like
7

@suman_18733097
can you please help me
can you please why explain why do we need to do soo many times mod for every step we add.
why cant we just add first like
example
array=[2,1]
queries = 2
initial sum=3
processing query 1=[2,1,2,1]===6
processing query 2=[2,1,2,1,2,1,2,1]====12
code :: sum=sum+sum;

then at the end
cout<<abs(sum)%1000000007;

note : i believe there is no need for rotation of the array since thats not req, so i just gave the above example without making any rotation since that makes no difference to the ans

8

I guess you misunderstood the subject of the discussion. This Discussion is about a different problem but has the same name as what you think.

You are referring to this problem (If I am not wrong).

Coming to your doubt

If you keep adding the elements, it results in Integer Overflow. It won’t fit in a long integer too. Also, why would someone add repeatedly if he/she can just multiply the sum with 2 for every query?

To overcome the overflow, we will reduce the value by taking modulo 10^9 + 7.

You can visit previous topics on Codechef discuss to understand why we take Modulo on large numbers, specifically, modulo 10^9 + 7 or 998,244,353.