Leetcode 1524: Number of Sub-arrays With Odd Sum
You are given an array of integers
arr. Your task is to count the number of subarrays whose sum is odd. Since the answer can be a large number, return it modulo (10^9 + 7).Problem
Approach
Steps
Complexity
Input: An array of integers `arr` is given as input.
Example: arr = [1, 3, 5]
Constraints:
• 1 <= arr.length <= 10^5
• 1 <= arr[i] <= 100
Output: Return the number of subarrays whose sum is odd, modulo (10^9 + 7).
Example: For arr = [1, 3, 5], the output is 4.
Constraints:
• The output is the number of subarrays with an odd sum modulo (10^9 + 7).
Goal: Count the number of subarrays with odd sums.
Steps:
• Iterate through the array and track the odd and even subarray sums.
• Swap the odd and even counts when an odd number is encountered.
• Sum the odd subarrays and return the result modulo (10^9 + 7).
Goal: The input size can be large, and the values of elements in the array can also be large.
Steps:
• 1 <= arr.length <= 10^5
• 1 <= arr[i] <= 100
Assumptions:
• The array is not empty and contains at least one element.
• The array contains integers within the given range.
• Input: arr = [1, 3, 5]
• Explanation: The subarrays are [1], [1, 3], [1, 3, 5], [3], [3, 5], [5]. Their sums are [1, 4, 9, 3, 8, 5], and the odd sums are [1, 9, 3, 5]. Thus, the answer is 4.
• Input: arr = [2, 4, 6]
• Explanation: All subarrays have even sums, so there are no odd-sum subarrays. Thus, the answer is 0.
Approach: To solve this problem, track the number of odd and even subarrays as we iterate through the array.
Observations:
• The sum of any subarray depends on whether the individual elements are odd or even.
• We need to count the odd sums by keeping track of the odd and even subarray counts at each step.
Steps:
• Initialize counters for odd and even subarray sums.
• Iterate through the array, swapping odd and even counts when encountering an odd number.
• Add the count of odd subarrays to the total sum.
• Return the result modulo (10^9 + 7).
Empty Inputs:
• No empty inputs allowed; the array has at least one element.
Large Inputs:
• Ensure the solution can handle large input sizes up to 10^5 elements.
Special Values:
• All elements are even or all elements are odd, which will affect the odd subarray count.
Constraints:
• Ensure to return the result modulo (10^9 + 7).
int numOfSubarrays(vector<int>& arr) {
int odd = 0, even = 0, sum = 0;
for(int x : arr) {
if (x % 2) {
swap(odd, even);
odd++;
} else even++;
sum = (sum + odd) % 1000000007;
}
return sum;
}
1 : Function Declaration
int numOfSubarrays(vector<int>& arr) {
This line declares the function `numOfSubarrays`, which takes a reference to an integer vector `arr` and returns an integer representing the number of subarrays with an odd sum.
2 : Variable Initialization
int odd = 0, even = 0, sum = 0;
Here, three variables are initialized: `odd` (counts odd subarrays), `even` (counts even subarrays), and `sum` (holds the total sum of odd subarrays encountered so far).
3 : Looping Through Array
for(int x : arr) {
This line starts a loop to iterate over each element `x` in the array `arr`.
4 : Condition Check (Odd Number)
if (x % 2) {
This condition checks if the current number `x` is odd by checking the remainder when divided by 2.
5 : Swap Odd and Even Counters
swap(odd, even);
Swaps the values of `odd` and `even` to switch the roles, as an odd number flips the parity of subarrays.
6 : Increment Odd Counter
odd++;
Increments the `odd` counter since the current element `x` is odd, meaning the subarrays formed with this element will have odd sums.
7 : Increment Even Counter
} else even++;
If the number is even, the `even` counter is incremented, as the subarrays formed with even numbers will continue to have even sums.
8 : Update Sum
sum = (sum + odd) % 1000000007;
Updates the total `sum` by adding the current `odd` count and taking the result modulo 1000000007 to prevent overflow and ensure large number handling.
9 : Return Statement
return sum;
Returns the final result stored in `sum`, which represents the number of subarrays with an odd sum.
Best Case: O(n)
Average Case: O(n)
Worst Case: O(n)
Description: The solution processes each element in the array once.
Best Case: O(1)
Worst Case: O(1)
Description: The solution uses a constant amount of extra space for counting odd and even sums.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus