Approach #1: Interval Stabbing [Accepted]
Intuition
Say N = 10
and A[2] = 5
. Then there are 5 rotations that are bad for this number: rotation indexes 0, 1, 2, 8, 9
 these rotations will cause this number to not get 1 point later.
In general, for each number in the array, we can map out what rotation indexes will be bad for this number. It will always be a region of one interval, possibly two if the interval wraps around (eg. 8, 9, 0, 1, 2
wraps around, to become [8, 9]
and [0, 1, 2]
.)
At the end of plotting these intervals, we need to know which rotation index has the least intervals overlapping it  this one is the answer.
Algorithm
First, an element like A[2] = 5
will not get score in (up to) 5 posiitons: when the 5 is at final index 0, 1, 2, 3, or 4. When we shift by 2, we'll get final index 0. If we shift 51 = 4
before this, this element will end up at final index 4. In general (modulo N), a shift of i  A[i] + 1
to i
will be the rotation indexes that will make A[i]
not score a point.
If we are trying to plot an interval like [2, 3, 4]
, then instead of doing bad[2]; bad[3]; bad[4];
, what we will do instead is keep track of the cumulative total: bad[2]; bad[5]++
. For "wraparound" intervals like [8, 9, 0, 1, 2]
, we will keep track of this as two separate intervals: bad[8], bad[10]++, bad[0], bad[3]++
. (Actually, because of our implementation, we don't need to remember the bad[10]++
part.)
At the end, we want to find a rotation index with the least intervals overlapping. We'll maintain a cumulative total cur
representing how many intervals are currently overlapping our current rotation index, then update it as we step through each rotation index.
Complexity Analysis

Time Complexity: , where is the length of
A
. 
Space Complexity: .
Analysis written by: @awice.