Skip to content

4044. Count Good Cyclic Rotations

Description

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 <= 105
  • 1 <= nums[i] <= 109
  • n is even.

Solutions

Solution 1: Sliding Window

Let \(n\) be the length of the array and \(m = n / 2\). First compute the sum \(l\) of the first \(m\) elements of the original array and the sum \(r\) of the last \(m\) elements. If \(l > r\), increment the answer by \(1\).

Then start from the original array and cyclically shift it left by one position, \(n - 1\) times in total. On the \(i\)-th shift (\(i\) starts from \(0\)), the first half loses \(\textit{nums}[i]\) and gains \(\textit{nums}[(i + m) \bmod n]\), while the second half does the opposite. Update \(l\) and \(r\) in \(O(1)\) time, and increment the answer whenever \(l > r\).

The time complexity is \(O(n)\) and the space complexity is \(O(1)\), where \(n\) is the length of the array \(\textit{nums}\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution:
    def countGoodRotations(self, nums: list[int]) -> int:
        n = len(nums)
        m = n // 2
        l = sum(nums[:m])
        r = sum(nums[m:])
        ans = int(l > r)
        for i in range(n - 1):
            l -= nums[i]
            r += nums[i]
            l += nums[(i + m) % n]
            r -= nums[(i + m) % n]
            ans += int(l > r)
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    public int countGoodRotations(int[] nums) {
        int n = nums.length;
        int m = n / 2;

        long l = 0, r = 0;
        for (int i = 0; i < m; i++) {
            l += nums[i];
        }
        for (int i = m; i < n; i++) {
            r += nums[i];
        }

        int ans = l > r ? 1 : 0;

        for (int i = 0; i < n - 1; i++) {
            l -= nums[i];
            r += nums[i];
            l += nums[(i + m) % n];
            r -= nums[(i + m) % n];
            ans += l > r ? 1 : 0;
        }

        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    int countGoodRotations(vector<int>& nums) {
        int n = nums.size();
        int m = n / 2;

        long long l = 0, r = 0;
        for (int i = 0; i < m; i++) {
            l += nums[i];
        }
        for (int i = m; i < n; i++) {
            r += nums[i];
        }

        int ans = l > r;

        for (int i = 0; i < n - 1; i++) {
            l -= nums[i];
            r += nums[i];
            l += nums[(i + m) % n];
            r -= nums[(i + m) % n];
            ans += l > r;
        }

        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
func countGoodRotations(nums []int) int {
    n := len(nums)
    m := n / 2

    var l, r int64
    for i := 0; i < m; i++ {
        l += int64(nums[i])
    }
    for i := m; i < n; i++ {
        r += int64(nums[i])
    }

    ans := 0
    if l > r {
        ans++
    }

    for i := 0; i < n-1; i++ {
        l -= int64(nums[i])
        r += int64(nums[i])
        l += int64(nums[(i+m)%n])
        r -= int64(nums[(i+m)%n])
        if l > r {
            ans++
        }
    }

    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
function countGoodRotations(nums: number[]): number {
    const n = nums.length;
    const m = Math.floor(n / 2);

    let l = 0,
        r = 0;
    for (let i = 0; i < m; i++) {
        l += nums[i];
    }
    for (let i = m; i < n; i++) {
        r += nums[i];
    }

    let ans = l > r ? 1 : 0;

    for (let i = 0; i < n - 1; i++) {
        l -= nums[i];
        r += nums[i];
        l += nums[(i + m) % n];
        r -= nums[(i + m) % n];
        ans += l > r ? 1 : 0;
    }

    return ans;
}

Comments