# Smallest Rotation With Highest Score

• It seems that this is not a "Interval Stabbing" problem
Please correct me if I am wrong.

"what we will do instead is keep track of the cumulative total: bad[2]--; bad[5]++. For "wrap-around" intervals like [8, 9, 0, 1, 2], we will keep track of this as two separate intervals: bad[8]--, bad[10]++, bad[0]--, bad[3]++. (Actually, because of our implementation, we don't need to remember the bad[10]++ part.)"

It totally went over my head.

• @Aakash_Ajay Hi I think i figure this out. It's tricky but brilliant. Let's say you have an array bad with index from 0 to 5. bad[2]--, bad[3]--, bad[4]--, makes the array looks like this:

So the -1 give an information that there is an interval [2,3,4]. To save time instead of this you will do bad[2]-- and bad[5]++ which result in:

and then you do a cumulative sum from i = 1 to end of array bad[i] += bad[i-1]:
.
It will be still beter time because the idea is that you put all the bad[left] and bad[right] first and then at the end make cumulative sum once. Small example: two intervals [1,2,3]; [3,4]:

• Hi there, I think there is a mistake in the explanation :

``````When we shift by 2, we'll get final index 0. ==> ok
If we shift 5-1 = 4 before this, this element will end up at final index 4. ==> seems wrong, we end up at index 6 !
``````

I think you meant that if we shift by 8, we end up at position 4

• Hello again :
I think the shifting position is always to be positive right ?
Else there is an issue with the clarity of the problem ?

``````In general (modulo N), a shift of abs( i - A[i] + 1 ) to i will be the rotation indexes that will make A[i] not score a point.
``````

• @bodziozet ya, I got your explanation, the logic is so elegant, it took time to digest in.

• ``````public int bestRotation(int[] a) {

int[] resultArray = new int[a.length];
int finalScore = 0;

for (int m = 0; m <= a.length - 1; m++) {
Integer new_index = 0;

for (int i = 0; i <= a.length - 1; i++) {
if ((i - a[m]) < 0) {
new_index = (i - a[m]) + (a.length);
} else {
new_index = (i - a[m]);
}
resultArray[new_index] = a[i];
}

int totalscore = 0;
for (int j = 0; j <= resultArray.length - 1; j++) {
if (resultArray[j] <= j) {
totalscore++;
}
}
if (totalscore > finalScore) {
finalScore = totalscore;
}
}
return finalScore;
}``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.