Count Subarrays With Even Odd Ratio II - Video Solutions
Super Hard💀DSA Question asked by Leetcode in Weekly Contest 513(Q4,4013)
Count Subarrays With Even Odd Ratio II - Video Solution
Watch 5 video solutions for Count Subarrays With Even Odd Ratio II, a hard level problem involving Array, Divide and Conquer, Binary Indexed Tree. This walkthrough by DSA with Kumar K has 492 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 <= 1051 <= nums[i] <= 1091 <= a, b <= 109​​​​​​​
Approach Overview
Problem Overview: You need to count the number of subarrays in which the ratio of even to odd numbers satisfies a given condition.
Approach 1: Brute Force (O(n^2))
Iterate through all possible subarrays and count the even and odd numbers in each. Check if the ratio meets the condition. This approach is straightforward but inefficient for large arrays.
Approach 2: Prefix Sum with Hash Map (O(n))
Use a prefix sum array to store cumulative counts of even and odd numbers. Employ a hash map to store the frequency of specific ratios. This allows you to efficiently count valid subarrays in linear time. This is the optimal approach for large datasets.
Recommended for interviews: Interviewers expect you to discuss the brute force approach to show understanding, but the optimal solution using prefix sum and hash map demonstrates advanced problem-solving skills.
Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force | O(n^2) | O(1) | Small arrays |
| Prefix Sum with Hash Map | O(n) | O(n) | Large arrays |