Prefix Array Sum Solution || C++ || O(n)
Let me illustrate an example for getting a better insight. Suppose,\n\nSizeof(A) = 10\nA[6] = 4.\nLet R be the rotational array.\n\nThen, 4 is acceptable for th
Let me illustrate an example for getting a better insight. Suppose,\n```\nSizeof(A) = 10\nA[6] = 4.\nLet R be the rotational array.\n\nThen, 4 is acceptable for the range of the indexes : A[4, ..., 9]\nIn terms of rotation, it is R[0, ..., 2] and R[7, ..., 9]   //All possible valid rotations\n```\n\nIn other words, the main idea is that we choose the intervals acceptable for a certain number and calculate them in terms of Rotations. \n```\nThe rotation with the highest valid values wins.\n```\nApparently, we will use a prefix sum to store the intervals, which will take only O(1), and then evaluate the prefix sum in the next iteration.\n\n```\nint bestRotation(vector<int>& a) {\n    vector<int> pref(a.size()+1);\n    auto push = [&] (int l, int r) -> void {\n        pref[l]++, pref[r+1]--;  //Just tweak the two endpoints \n    };\n\n    int n = a.size();\n    for(int i = 0 ;  i< n; i++) {\n\t\tif(a[i] <= i) {  //We will need to split it into two, as shown in the upper example.\n            push(0, i-a[i]);\n            push(i+1, n-1);\n        } else {    //a[i] > i  \n            push(i+1, i+1+(n-1-a[i]));\n        }\n    }\n    int mx = pref[0], mx_val = 0;\n\t//mx_val holds the index rotation number\n\t\n    for(int i = 1;  i < n; i++) {\n        pref[i] += pref[i-1];\n        \n        if(mx < pref[i]) {\n            mx = pref[i];\n            mx_val = i;\n        }\n    }\n    return mx_val;\n}\n```
['C']