Count Subarrays With Even Odd Ratio I - Video Solutions
Count Subarrays With Even Odd Ratio I | LeetCode 4011 | Weekly Contest 513 | Java | Developer Coder
Count Subarrays With Even Odd Ratio I - Video Solution
Watch 3 video solutions for Count Subarrays With Even Odd Ratio I, a medium level problem involving Array, Divide and Conquer, Binary Indexed Tree. This walkthrough by Developer Coder has 142 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
You are given an integer array nums and two integers a and b.
For a subarray, let:
xbe the number of even elements.ybe 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, andx / 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 <= 10001 <= nums[i] <= 10001 <= a, b <= 1000
Approach Overview
Problem Overview: You need to count the number of subarrays in which the ratio of even to odd elements meets a specific condition.
Approach 1: Enumerate Subarrays (O(n^2))
Iterate through all possible subarrays by fixing the start and end indices. For each subarray, count the number of even and odd elements and check if their ratio matches the condition. This approach is straightforward but inefficient for large arrays. Use this when simplicity is more important than performance.
Recommended for interviews: Interviewers expect you to discuss the brute force approach first to show understanding of the problem. However, they prefer the optimal solution to demonstrate your ability to optimize code. Enumerate subarrays is the brute force approach here.
Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Enumerate Subarrays | O(n^2) | O(1) | Small arrays or when simplicity is needed |