Last updated on October 9th, 2024 at 06:25 pm
Here, We see Smallest Rotation with Highest Score LeetCode Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc. with different approaches.
List of all LeetCode Solution
Topics
Array, Math
Level of Question
Hard
Smallest Rotation with Highest Score LeetCode Solution
Table of Contents
Problem Statement
You are given an array nums
. You can rotate it by a non-negative integer k
so that the array becomes [nums[k], nums[k + 1], ... nums[nums.length - 1], nums[0], nums[1], ..., nums[k-1]]
. Afterward, any entries that are less than or equal to their index are worth one point.
- For example, if we have
nums = [2,4,1,3,0]
, and we rotate byk = 2
, it becomes[1,3,0,2,4]
. This is worth3
points because1 > 0
[no points],3 > 1
[no points],0 <= 2
[one point],2 <= 3
[one point],4 <= 4
[one point].
Return the rotation index k
that corresponds to the highest score we can achieve if we rotated nums
by it. If there are multiple answers, return the smallest such index k
.
Example 1: Input: nums = [2,3,1,4,0] Output: 3 Explanation: Scores for each k are listed below: k = 0, nums = [2,3,1,4,0], score 2 k = 1, nums = [3,1,4,0,2], score 3 k = 2, nums = [1,4,0,2,3], score 3 k = 3, nums = [4,0,2,3,1], score 4 k = 4, nums = [0,2,3,1,4], score 3 So we should choose k = 3, which has the highest score Example 2: Input: nums = [1,3,0,2,4] Output: 0 Explanation: nums will always have 3 points no matter how it shifts. So we will choose the smallest k, which is 0.
1. Smallest Rotation with Highest Score Leetcode Solution C++
class Solution { public: int bestRotation(vector<int>& nums) { const int N = nums.size(); vector<int> tmp(N+1, 0); for (int i(0); i < N; ++i) { if (nums[i] <= i) { tmp[0] += 1; tmp[i-nums[i]+1] -= 1; tmp[i+1] += 1; tmp[N] -= 1; } else { tmp[i+1] += 1; tmp[N-nums[i]+i+1] -= 1; } } int maxc = INT_MIN; int maxK = -1; int cur = 0; for (int i(0); i < N; ++i) { cur += tmp[i]; if (cur > maxc) { maxc = cur; maxK = i; } } return maxK; } };
2. Smallest Rotation with Highest Score Leetcode Solution Java
class Solution { public int bestRotation(int[] nums) { final int size = nums.length; int[] rsc = new int[size]; for(int i = 0; i < size - 1; i++) { int value = nums[i]; int downPos = (i + 1 + size - value) % size; rsc[downPos]--; } int value = nums[size-1]; if( value != 0 ) rsc[size - value]--; int bestk = 0; int bestscore = rsc[0]; int score = rsc[0]; for(int i = 1; i < nums.length; i++) { score += rsc[i] + 1; if( score > bestscore ) { bestk = i; bestscore = score; } } return bestk; } }
3. Smallest Rotation with Highest Score Leetcode Solution JavaScript
var bestRotation = function (nums) { let acc = new Uint32Array(100001); let n = nums.length; acc.fill(0, 0, n + 1); for (let i = 0; i < n; ++i) { ++acc[Math.min(i + 1, Math.max(0, i - nums[i] + 1))]; } let bestInd = 0; let bestCnt = n - acc[0]; let currCnt = bestCnt; for (let i = 1; i < n; ++i) { currCnt -= acc[i]; if (nums[i - 1] < n) { ++currCnt; let exp = i + n - nums[i - 1]; if (exp < n) ++acc[exp]; } if (currCnt > bestCnt) { bestCnt = currCnt; bestInd = i; } } return bestInd; };
4. Smallest Rotation with Highest Score Leetcode Solution Python
class Solution(object): def bestRotation(self, nums): n = len(nums) change = [1] * n for i, num in enumerate(nums): change[(i - num + 1) % n] -= 1 for i in range(1, n): change[i] += change[i - 1] return change.index(max(change))