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}\).

Python3JavaC++GoTypeScript

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

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

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

4011. Count Subarrays With Even Odd Ratio I

Description

Solutions

Solution 1: Enumerate Subarrays

Comments