Count Subarrays With Equal Numbers of Even and Odd Elements
Company: Microsoft
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
Given an array of integers, count the subarrays that contain exactly as many even numbers as odd numbers.
### Function Signature
```python
def count_balanced_subarrays(nums: list[int]) -> int:
```
### Rules
- A subarray is a contiguous, nonempty slice `nums[i..j]` with `0 <= i <= j < len(nums)`. Subarrays with a different start or end index are counted separately, even when they hold the same values.
- A value is even when it is divisible by 2 and odd otherwise. Zero is even, and negative values follow the same rule: `-4` is even and `-3` is odd.
- A subarray is counted when its number of even elements equals its number of odd elements, so every counted subarray has even length.
- Return the number of counted subarrays as a single integer.
### Constraints
- `1 <= len(nums) <= 10^5`
- `-10^9 <= nums[i] <= 10^9`
- The answer can exceed `2^31 - 1`: for `10^5` elements with alternating parity it is 2,500,000,000. Use a 64-bit integer in languages with fixed-width types; the answer always stays below `2^53`.
### Examples
**Example 1**
```text
Input: nums = [1, 2, 3, 4]
Output: 4
```
The three subarrays of length 2, `[1, 2]`, `[2, 3]` and `[3, 4]`, each hold one odd and one even number, and the whole array holds two of each. No subarray of odd length can be balanced.
**Example 2**
```text
Input: nums = [2, 4, 6]
Output: 0
```
Every element is even, so no subarray contains an odd number.
**Example 3**
```text
Input: nums = [5, -2, 0, 7, 9, 8]
Output: 7
```
Here `-2`, `0` and `8` are even. The balanced subarrays are `[5, -2]`, `[0, 7]`, `[9, 8]`, `[5, -2, 0, 7]`, `[-2, 0, 7, 9]`, `[0, 7, 9, 8]` and the whole array. Subarrays such as `[-2, 0]` and `[7, 9]` are not balanced.
Overview: Count the contiguous subarrays of an integer array that contain as many even numbers as odd numbers. Tests turning a balance condition over all subarrays into efficient counting, correct parity for negative values and zero, and using a 64-bit result for large inputs.
Given an array of integers `nums`, count the subarrays that contain exactly as many even numbers as odd numbers.
A subarray is a contiguous, nonempty slice `nums[i..j]` with `0 <= i <= j < len(nums)`. Subarrays with a different start or end index are counted separately, even when they hold the same values.
A value is even when it is divisible by 2 and odd otherwise. Zero is even, and negative values follow the same rule: `-4` is even and `-3` is odd.
A subarray is counted when its number of even elements equals its number of odd elements, so every counted subarray has even length. Return the number of counted subarrays as a single integer.
The answer can exceed 2^31 - 1: for 10^5 elements with alternating parity it is 2,500,000,000. Return it as a 64-bit integer (`long` in Java, `long long` in C++); it always stays below 2^53.
**Example 1**
Input: nums = [1, 2, 3, 4]
Output: 4
The three subarrays of length 2, `[1, 2]`, `[2, 3]` and `[3, 4]`, each hold one odd and one even number, and the whole array holds two of each. No subarray of odd length can be balanced.
**Example 2**
Input: nums = [5, -2, 0, 7, 9, 8]
Output: 7
Here `-2`, `0` and `8` are even. The balanced subarrays are `[5, -2]`, `[0, 7]`, `[9, 8]`, `[5, -2, 0, 7]`, `[-2, 0, 7, 9]`, `[0, 7, 9, 8]` and the whole array. Subarrays such as `[-2, 0]` and `[7, 9]` are not balanced.
**Constraints**
- `1 <= len(nums) <= 10^5`
- `-10^9 <= nums[i] <= 10^9`
- The answer can exceed `2^31 - 1` but always stays below `2^53`.
Constraints
- 1 <= len(nums) <= 10^5
- -10^9 <= nums[i] <= 10^9
- The answer can exceed 2^31 - 1 (2,500,000,000 for 10^5 elements with alternating parity); use a 64-bit integer (long in Java, long long in C++). It always stays below 2^53.
Examples
Input: ([1, 2, 3, 4],)
Expected Output: 4
Explanation: Source Example 1: the three length-2 windows plus the whole array.
Input: ([2, 4, 6],)
Expected Output: 0
Explanation: Source Example 2: every element is even, so no subarray holds an odd number.
Hints
- Only whether each value is even or odd matters; zero is even and negative values follow the same rule.
- With up to 10^5 elements there are about 5 * 10^9 subarrays, so checking each one separately is too slow.
- Remember that a balanced subarray may start at index 0, and that equal values at different positions form separate subarrays.