Welcome to Subscribe On Youtube

4011. Count Subarrays With Even Odd Ratio I

Description

You are given an integer array nums and two integers a and b.

For a subarray, let:

  • x be the number of even elements.
  • y be the number of odd elements.

The ratio of even to odd elements in a subarray is defined as x / y, where ratios are compared by their exact rational values.

A subarray is considered valid if:

  • y > 0, and
  • x / y <= a / b.

Return the number of valid subarrays in nums.

 

Example 1:

Input: nums = [1,2,1,2], a = 3, b = 2

Output: 7

Explanation:

The following are the valid subarrays:

Subarray Values Even Count Odd Count Ratio
nums[0..0] [1] 0 1 0 / 1
nums[0..1] [1, 2] 1 1 1 / 1
nums[0..2] [1, 2, 1] 1 2 1 / 2
nums[0..3] [1, 2, 1, 2] 2 2 2 / 2
nums[1..2] [2, 1] 1 1 1 / 1
nums[2..2] [1] 0 1 0 / 1
nums[2..3] [1, 2] 1 1 1 / 1

Thus, the number of valid subarrays is 7.

Example 2:

Input: nums = [2,2,1], a = 2, b = 1

Output: 3

Explanation:

The following are the valid subarrays:

Subarray Values Even Count Odd Count Ratio
nums[0..2] [2, 2, 1] 2 1 2 / 1
nums[1..2] [2, 1] 1 1 1 / 1
nums[2..2] [1] 0 1 0 / 1

Thus, the number of valid subarrays is 3.

Example 3:

Input: nums = [2,2,2], a = 1, b = 1

Output: 0

Explanation:

Every subarray contains 0 odd numbers, so no subarray is valid.

 

Constraints:

  • 1 <= nums.length <= 1000
  • 1 <= nums[i] <= 1000
  • 1 <= a, b <= 1000

Solutions

Solution 1: Enumerate Subarrays

Thinking

For $n\le 1000$ there are $O(n^2)$ subarrays, so enumerating both endpoints is acceptable.

With the left end fixed we extend the right end, counting odd entries $y$; the even count is the length minus $y$. The test $\frac{x}{y}\le\frac{a}{b}$ is meaningful only for $y>0$, matching the floating-point comparison in the code, and subarrays with $y=0$ are skipped.

Prefix sums and Fenwick trees are unnecessary; the double loop already counts every valid subarray.

We enumerate the left endpoint $i$ of the subarray, then extend the right endpoint $j$ to the right while maintaining the count of odd numbers $y$ in the subarray. The count of even numbers is then $x = j - i + 1 - y$.

If $y > 0$ and $\frac{x}{y} \le \frac{a}{b}$, the subarray is valid. To avoid precision issues from floating-point arithmetic, we can transform the condition into the equivalent integer comparison $x \times b \le y \times a$.

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

  • class Solution {
    public int countRatioSubarrays(int[] nums, int a, int b) {
        int n = nums.length;
        long ans = 0;

        for (int i = 0; i < n; i++) {
            int y = 0;

            for (int j = i; j < n; j++) {
                y += nums[j] % 2;
                int x = j - i + 1 - y;

                if (y > 0 && (long) x * b <= (long) y * a) {
                    ans++;
                }
            }
        }

        return (int) ans;
    }
}

  • class Solution {
public:
    int countRatioSubarrays(vector<int>& nums, int a, int b) {
        int n = nums.size();
        long long ans = 0;

        for (int i = 0; i < n; i++) {
            int y = 0;

            for (int j = i; j < n; j++) {
                y += nums[j] % 2;
                int x = j - i + 1 - y;

                if (y > 0 && 1LL * x * b <= 1LL * y * a) {
                    ans++;
                }
            }
        }

        return ans;
    }
};

  • class Solution:
    def countRatioSubarrays(self, nums: list[int], a: int, b: int) -> int:
        ans = 0
        n = len(nums)
        for i in range(n):
            y = 0
            for j in range(i, n):
                y += nums[j] % 2
                x = j - i + 1 - y
                if y and (x / y) <= (a / b):
                    ans += 1
        return ans


  • func countRatioSubarrays(nums []int, a int, b int) int {
	n := len(nums)
	var ans int64 = 0

	for i := 0; i < n; i++ {
		y := 0

		for j := i; j < n; j++ {
			y += nums[j] % 2
			x := j - i + 1 - y

			if y > 0 && int64(x)*int64(b) <= int64(y)*int64(a) {
				ans++
			}
		}
	}

	return int(ans)
}


  • function countRatioSubarrays(nums: number[], a: number, b: number): number {
    const n = nums.length;
    let ans = 0;

    for (let i = 0; i < n; i++) {
        let y = 0;

        for (let j = i; j < n; j++) {
            y += nums[j] % 2;
            const x = j - i + 1 - y;

            if (y > 0 && x * b <= y * a) {
                ans++;
            }
        }
    }

    return ans;
}

All Problems

All Solutions