yesnomaybe's blog

Can minimum number of rotations required to get the same string be greater than len/2 and less than len ever?
By yesnomaybe, history, 5 years ago, In English

Given string S, and let K be the minimum number of rotations required to get the same string.

For Example: (1) For S = "aaaa", K = 1 (2) For S = "abcabc", K = 3 (3) For S = "abcdef", K = 6

Now my question is, can there be any string for which K > len(S)/2 and K < len(S) ? If not, can someone please help me prove it?

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it +9 Vote: I do not like it

In your example (3), K is greater than len(S) / 2.

You asked the wrong question?

→ Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    Sorry I asked the wrong question. Have updated the question now. Can you please check? Can K > len(S)/2 && K < len(S)?

    → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by yesnomaybe (previous revision, new revision, compare).

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by yesnomaybe (previous revision, new revision, compare).

→ Reply
»
5 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Not possible, because K can only be divisor of N, and there is no such divisor greater than N/2 and less than N.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you please share the intuition behind why K needs to be divisor of N?

    → Reply