Skip to main content
Talentd

Count Subarrays With Even Odd Ratio I - Solution & Explanation

MediumArrayDivide and ConquerBinary Indexed TreeSegment Tree6 min read
Practice this problem

Problem Statement

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

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.

Solution

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 nums.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Enumerate SubarraysO(n^2)O(1)Small arrays or when simplicity is needed

Video Solution

Count Subarrays With Even Odd Ratio I | LeetCode 4011 | Weekly Contest 513 | Java | Developer Coder • Developer Coder • 142 views views

Watch 2 more video solutions →

Frequently Asked Questions

Is Count Subarrays With Even Odd Ratio I easy or hard?
The problem is rated Medium with a 60% acceptance rate. It requires understanding of subarrays and basic iteration techniques.
Count Subarrays With Even Odd Ratio I Python/Java solution
The solution involves nested loops to enumerate subarrays and count even and odd elements. Code is available in Python, Java, C++, Go, and TypeScript on FleetCode.
How to solve Count Subarrays With Even Odd Ratio I in O(n)?
Currently, the optimal solution involves enumerating subarrays with O(n^2) complexity. There is no known O(n) solution for this problem.
What is the best approach for Count Subarrays With Even Odd Ratio I?
The best approach is to enumerate all subarrays and check the ratio of even to odd elements. This brute force method ensures correctness but is inefficient for large arrays.
Is Count Subarrays With Even Odd Ratio I asked at Google/Amazon/Meta?
While not explicitly tagged, problems involving subarray enumeration and ratio checks are common in interviews at top tech companies.
What data structure is used in Count Subarrays With Even Odd Ratio I?
No specific data structure is required. The solution involves iterating through the array and checking subarrays directly.
What is the time complexity of Count Subarrays With Even Odd Ratio I?
The time complexity is O(n^2) when using the enumerate subarrays approach, as you need to check all possible subarrays.

Ready to solve this problem?

Practice Count Subarrays With Even Odd Ratio I with our built-in code editor and test cases.

Practice on FleetCode
Previous

Count Subarrays With Even Odd Ratio II