Scala Interval Stabbing and  Brute Force C and Python (numpy)
\nobject Solution {\n    // I found that interval concept is easier to understand than the gain/lost counting\n    // find the interval of [k1,k2) where for eac
```\nobject Solution {\n    // I found that interval concept is easier to understand than the gain/lost counting\n    // find the interval of [k1,k2) where for each value at nums index i , [k1,k2) range will cause point lost (the bad range), then find the K which falls into the bad range least number of times among all intervals\n    def bestRotation(nums: Array[Int]): Int = {\n        val N=nums.length\n        val interval=Array.fill[Int](N) {0}\n        for (i <- 0 until N)  {\n            // the key point is that we can\'t mark each element within the interval one by one, that would have caused O(N^2) time. by marking left with -1, marking right (non-inclusive point) with +1, when we later run the cumsum, the -1 will carry over until it meets right index which offsets the change to 0.\n           interval((i-nums(i)+1+N)%N) -=1 \n           interval((i+1)%N) +=1 //when the original ith number is rotated from index 0 to index n-1. The number of rotations required is (i + 1) % n\n            //if ( (i-nums(i)+1+N)%N > (i+1)%N) interval(0) -=1 // this seems to be optional?\n        }\n        /*\n        var res,curr=0\n        var max= -N\n        for (i <- 0 until N) {\n            curr += interval(i)\n            if (curr>max) {\n                max=curr\n                res=i\n            }\n        } \n        res\n        */\n        for (i <- 1 until N) interval(i) += interval(i-1)\n        interval.indexOf(interval.max)\n    }\n    \n    //inspire by @lee215 whose idea is 1. a point is gained with every rotation; 2. a point is lost starting from index position i-nums(i)+1-N, wrapp around if needed. \n    def bestRotationLee(nums: Array[Int]): Int = {\n        val N=nums.length\n        val change=Array.fill[Int](N) {1}\n        for (i <- 0 until N)  {\n            change((i-nums(i)+1+N)%N) -=1\n        }\n        for (i <- 1 until N) change(i) += change(i-1)\n        change.indexOf(change.max)\n    }\n}\n```\n\nPython Brute Force, TLE for large test cases. But it still provides the baseline thinking , before going to the more tricky and advanced approach.\n```\n# Inspired @StefanPochmann\nclass Solution:\n    def bestRotation(self, A):\n        import numpy as np\n        n = len(A)\n        a = np.array(2 * A) # 2*A copies A (double the size) and np.array() stores it as np array\n        nr = np.arange(n)\n        return max(range(n), key=lambda k: np.count_nonzero(a[k:k+n] <= nr))\n```\n\nHere is C in Brute Force, this is the first thing that came across my mind, though it\'s O(N^2) time:\n```\nint bestRotation(int* A, int N){\n    int best_score = 0, best_K = 0, score;\n    for (int K = 0; K < N; K++) {\n        score = 0;\n        for (int i = 0; i < N; i++)\n            if (A[(K + i) % N] <= i) score++;\n        if (score > best_score) {\n            best_K = K;\n            best_score = score;\n        }\n    }\n    return best_K;\n}\n```
[]