Easy c++ Solution O(n) concise well commented and explanation
\n// We are considering two cases :\n//  1. when nums[i]<=i\n//  2. whem nums[i]>i \n\n\n//  Lets calculate good rotations for both cases now ...... Good roatio
```\n// We are considering two cases :\n//  1. when nums[i]<=i\n//  2. whem nums[i]>i \n\n\n//  Lets calculate good rotations for both cases now ...... Good roations are those which will give us score \n\n//  for case 1 , that is nums[i]<=i \n//  if we rotate 1 times then it will go to i-1 \n//  if we rotate again it will go to i-2  \n//  What will be the good indices for nums[i] ?? all the indexes greater or equal to nums[i] and we are at i right now so to reach i what we need is i-nums[i] , we want nums[i] to be less than index so from  0 - (i-nums[i]) is valid but the indexes after the i will also add to score so to consider them we will take i - (n-1)\n\n//Now for case 2 , that is nums[i]>i\n//  if we rotate 1 times then it will go to i-1 \n//  if we rotate again it will go to i-2  \n// What will be the good indices for nums[i] ?? all the indexes greater or equal to nums[i] \n// currently nums[i]>i means we need to shift nums[i] to right side and for that how many rotations we need atlead? i+1 and what are the max to reach the place where nums[i]=i , its how much nums[i] is ahead and ie  nums[i] - i to calc from left side lets substract from by n so now it becomes n-nums[i]+i , so good rotations are (i+1) - (n-(nums[i]-i)) \n\n// Now we have good rotations for every number , lets just calculate which rotation brings max score which is similar to the gfg problem \n  \n//       problem nume : powerfull interger\n//      from contest  weekly-interview-series-76\n\n\n\n\n\n\nclass Solution {\npublic:\n    int bestRotation(vector<int>& nums) {\n        \n        vector<pair<int,int>>goodIndices;\n        map<int,int>mp;\n        \n        for(int i=0;i<nums.size();i++)\n        if(nums[i]<=i)\n        goodIndices.push_back({0,i-nums[i]}) , goodIndices.push_back({i+1,nums.size()-1});\n        else\n        goodIndices.push_back({i+1 , i+ (nums.size()-nums[i])});\n        \n        for(auto i:goodIndices)\n        mp[i.first]++ , mp[i.second+1]--;\n        \n        int tempsum = 0 , rotations=0 , sum=0;\n        for(int i=0;i<nums.size();i++)\n        tempsum+=mp[i] , rotations=tempsum>sum?i:rotations  , sum=max(tempsum,sum);\n        \n        return rotations;\n    }\n};\n```\n
['Array', 'C', 'Prefix Sum']