Can anyone explain on 2Len -1 logic?


#1

In the editorial it is written like below:

With respect to a single string, the total number of bits rotated after N operations is 1+2+3+….+N which is (N*(N+1))/2.
We get back the original string only when the total number of rotated bits is a multiple of the length of the string S(LEN).

This can be done in O(N) time for each string (Summation of length of all strings is <= 1e6), by finding all (N (N+1))/2 where N starts from 1 and goes upto (2 LEN-1).

I understood the (N*(N+1))/2 logic but could not understand how it relates to 2* LEN - 1? Why are we checking no of rotation to be a multiple of LEN till 2*LEN -1?


#2

Suppose for a string s of length n we want to find the minimum value of i so that after i operations s return back to its original state. So, what can be the maximum value of i?

Let’s consider two cases,

  1. n is odd: If n is odd then total number of bits rotated after n - 1 operations is 1 + 2 + … + (n - 1) which is ((n - 1) * n)/2. Since n is odd so, n - 1 is divisible by 2 and the sum is ((n - 1)/2) * n which is a multiple of n.
  2. n is even: If n is even then total number of bits rotated after 2n - 1 operations is 1 + 2 + … + (2n - 1) which is ((2n - 1) * 2n)/2 which is a multiple of n.

So, if n is odd we need to check till n - 1, otherwise, we need to check till 2n - 1.