Welcome to Subscribe On Youtube

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

Thinking

A rotation is good only when the first half-sum is strictly larger than the second. Resumming both halves every time would be quadratic.

A left shift drops $\textit{nums}[i]$ from the first half and receives $\textit{nums}[(i+m)\bmod n]$; the second half does the opposite. Both sums therefore update in $O(1)$.

Starting from the original array we rotate $n$ times and count how often $l>r$.

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}$.

  • 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;
    }
}

  • 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;
    }
};

  • 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


  • 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
}


  • 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;
}

All Problems

All Solutions