Smallest Rotation with Highest Score in C++

Suppose we have an array A, we may rotate it by a K so that the array becomes A[K], A[K+1], A{K+2], ... A[A.length - 1], A[0], A[1], ..., A[K-1]. Then, any entries that are less than or equal to their index are worth 1 point.

So for example, let we have an array [2, 4, 1, 3, 0], and we rotate by K = 2, it becomes [1, 3, 0, 2, 4]. This is worth 3 points because 1 > 0 [gain no point], 3 > 1 [gain no point], 0 <= 2 [gain one point], 2 <= 3 [gain one point], 4 <= 4 [gain one point].

We have to find K, for which, we will get the highest score. If there are multiple answers, return the smallest such index K. So, if the input is like K = 2, then the answer will be 5.

So if the input is like [2,3,1,5,1], then output will be 3., this is because −

Answer will be 3.

To solve this, we will follow these steps −

• ret := 0
• n := size of A
• Define an array cnt of size n
• for initialize i := 0, when i < n, update (increase i by 1), do −
  • if A[i] <= i, then −
    • minI := 0, (increase cnt[minI] by 1)
    • maxI := i - A[i]
    • if maxI + 1 < n, then −
      • cnt[maxI + decrease 1] by 1
    • if i + 1 < n, then −
      • cnt[i + increase 1] by 1
  • Otherwise
    • if A[i] >= n, then −
      • Ignore following part, skip to the next iteration
    • minI := i + 1
    • (increase cnt[minI] by 1)
    • maxi := i + (n - A[i])
    • if maxi + 1 < n, then −
      • cnt[maxi + decrease 1] by 1
• maxCnt := -1, temp := 0
• for initialize i := 0, when i < n, update (increase i by 1), do −
  • temp := temp + cnt[i]
  • if temp > maxCnt, then −
    • maxCnt := temp
    • ret := i
• return ret

Let us see the following implementation to get better understanding −

Example

 Live Demo

#include <bits/stdc++.h> using namespace std; class Solution { public:    int bestRotation(vector<int>& A) {       int ret = 0;       int n = A.size();       vector <int> cnt(n);       for(int i = 0; i < n; i++){          if(A[i] <= i){             int minI = 0;             cnt[minI]++;             int maxI = i - A[i];             if(maxI + 1 < n) cnt[maxI + 1]--;             if(i + 1 < n) cnt[i + 1]++;          }else{             if(A[i] >= n) continue;             int minI = i + 1;             cnt[minI]++;             int maxi = i + (n - A[i]);             if(maxi + 1 < n)cnt[maxi + 1]--;          }       }       int maxCnt = -1;       int temp = 0;       for(int i = 0; i < n; i++){          temp += cnt[i];          if(temp > maxCnt){             maxCnt = temp;             ret = i;          }       }       return ret;    } }; main(){    Solution ob;    vector<int> v = {2,3,1,5,1};    cout << (ob.bestRotation(v)); }

Input

[2,3,1,5,1]

Output

3