You are given an integer array nums of even length n.
A cyclic rotation of nums is obtained by choosing a prefix of nums whose length is between 0 and n - 1 (inclusive), and moving it to the end of the array while preserving the order of all elements.
A cyclic rotation is good if the sum of its first n / 2 elements is strictly greater than the sum of its last n / 2 elements.
Return the number of cyclic rotations of nums that are good.
Example 1:
Input: nums = [1,2,3,4,5,6]
Output: 3
Explanation:
The cyclic rotations of nums are:
| Cyclic rotation | Sum of first n / 2 elements |
Sum of last n / 2 elements |
|---|---|---|
[1, 2, 3, 4, 5, 6] |
1 + 2 + 3 = 6 |
4 + 5 + 6 = 15 |
[2, 3, 4, 5, 6, 1] |
2 + 3 + 4 = 9 |
5 + 6 + 1 = 12 |
[3, 4, 5, 6, 1, 2] |
3 + 4 + 5 = 12 |
6 + 1 + 2 = 9 |
[4, 5, 6, 1, 2, 3] |
4 + 5 + 6 = 15 |
1 + 2 + 3 = 6 |
[5, 6, 1, 2, 3, 4] |
5 + 6 + 1 = 12 |
2 + 3 + 4 = 9 |
[6, 1, 2, 3, 4, 5] |
6 + 1 + 2 = 9 |
3 + 4 + 5 = 12 |
The first half has a greater sum than the second half for 3 rotations. Thus, the answer is 3.
Example 2:
Input: nums = [1,2,1,2]
Output: 0
Explanation:
The cyclic rotations of nums are:
| Cyclic rotation | Sum of first n / 2 elements |
Sum of last n / 2 elements |
|---|---|---|
[1, 2, 1, 2] |
1 + 2 = 3 |
1 + 2 = 3 |
[2, 1, 2, 1] |
2 + 1 = 3 |
2 + 1 = 3 |
[1, 2, 1, 2] |
1 + 2 = 3 |
1 + 2 = 3 |
[2, 1, 2, 1] |
2 + 1 = 3 |
2 + 1 = 3 |
No cyclic rotation is good because the two sums are equal for every rotation. Thus, the answer is 0.
Constraints:
2 <= n == nums.length <= 1051 <= nums[i] <= 109n is even.total be the sum of all elements and first be the sum of the first half of a rotation. The rotation is good exactly when first > total - first.first using a circular sliding window of length n / 2. Moving to the next rotation removes one element from the window and adds one element.[1,2,3,4,5,6]
[1,2,1,2]