title: Counting the number of moves for sorting an array if only unit shift are allowed
body: <p>So, I have an array containing integers. I need to sort it. However, the only operation I can perform is a unit shift. That is, I can move the last element of the sequence to its beginning.</p>
  
  <pre><code>          `a1, a2, ..., an → an, a1, a2, ..., an - 1.`
  </code></pre>
  
  <p>what is the minimum number of operations that I need to sort the sequence?</p>
  
  <p>The number of integers in the array can be upto 10^5. And each integer individual value can be 10^5 too. Also, if array is already sorted, print 0 else if array cannot be sorted by unit shifts, print -1. </p>
  
  <p>The solution that I thought of: </p>
  
  <ol>
  <li>Check if array is sorted or not. </li>
  <li>If array is sorted, print 0 else</li>
  <li>Set count = 0</li>
  <li>Rotate array by one unit and increment count.</li>
  <li>Check if array is sorted: if yes, print count and break, else</li>
  <li>repeat steps 4-5 till count &lt; (total integers in array).</li>
  </ol>
  
  <p>Now, the above solution has a time complexity of O(n^2). Because, I am checking for each individual element if array is sorted and this checking takes O(n) time, and I have n elements, so that makes it O(n^2). </p>
  
  <p>Can anyone suggest me some other better approach?
  Thanks!</p>
  
  <p>PS: I tried really hard thinking of some other approach. I reached uptill counting inversions, but that doesn't really help. </p>