Number of Sub-arrays With Odd Sum
#777 Most AskedMedium
Number of Sub-arrays With Odd Sum #777 Most Asked
Medium
9 views
Topics:
ArraysDynamic Programming
Given an array of integers arr, return the number of subarrays with an odd sum.
Since the answer can be very large, return it modulo 109 + 7.
Example 1:
Input: arr = [1,3,5] Output: 4 Explanation: All subarrays are [[1],[1,3],[1,3,5],[3],[3,5],[5]] All sub-arrays sum are [1,4,9,3,8,5]. Odd sums are [1,9,3,5] so the answer is 4.
Example 2:
Input: arr = [2,4,6] Output: 0 Explanation: All subarrays are [[2],[2,4],[2,4,6],[4],[4,6],[6]] All sub-arrays sum are [2,6,12,4,10,6]. All sub-arrays have even sum and the answer is 0.
Example 3:
Input: arr = [1,2,3,4,5,6,7] Output: 16
Constraints:
1 <= arr.length <= 1051 <= arr[i] <= 100
Solution
Clarifying Questions
When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:
- What is the maximum size of the input array `arr`, and what is the range of values for the integers within the array?
- Can the array `arr` contain negative numbers or zero values?
- If the input array `arr` is empty, what should the function return?
- Are we only concerned with contiguous sub-arrays, or can non-contiguous selections be considered?
- Could you provide a small example input and the expected output to ensure my understanding of the problem is correct?
Brute Force Solution
Approach
The brute force method for this problem involves examining every possible group of consecutive numbers within the given list. For each of these groups, we calculate the sum and determine if it's odd. By checking every possible group, we are guaranteed to find all the sub-arrays with an odd sum.
Here's how the algorithm would work step-by-step:
- Consider the first number in the list as a group by itself.
- Calculate the sum of this single number.
- Check if that sum is odd. If it is, count it.
- Now, consider the first two numbers as a group.
- Calculate the sum of these two numbers.
- Check if that sum is odd. If it is, count it.
- Continue this process, adding one more number to the group each time, until you've included all the numbers in the list in one big group, checking if that group's sum is odd.
- Next, start the process again, but this time begin with the second number in the list as the first number in your groups.
- Repeat the same process of forming larger and larger groups, calculating the sum and checking if it's odd.
- Keep doing this, each time starting with the next number in the original list, until you've started a group with every number in the original list.
- The final count is the total number of groups you found with an odd sum.
Code Implementation
def number_of_subarrays_with_odd_sum_brute_force(numbers):
number_of_odd_sum_subarrays = 0
array_length = len(numbers)
for start_index in range(array_length):
current_subarray_sum = 0
for end_index in range(start_index, array_length):
# Sum the current group of numbers
current_subarray_sum += numbers[end_index]
# Check if the sum is odd
if current_subarray_sum % 2 != 0:
# Increment if it is
number_of_odd_sum_subarrays += 1
return number_of_odd_sum_subarraysBig(O) Analysis
Time Complexity
O(n²) – The algorithm iterates through each element of the input array of size n. For each element, it calculates the sum of all sub-arrays starting from that element. This involves an inner loop that iterates from the starting element to the end of the array. Therefore, in the worst case, the number of calculations approximates to n + (n-1) + (n-2) + ... + 1 which is roughly n * (n+1) / 2. Simplifying this, we get a time complexity of O(n²).
Space Complexity
O(1) – The provided solution iterates through sub-arrays and calculates their sums. It only uses a few variables to keep track of the current sub-array's sum and the overall count of odd-sum sub-arrays. No auxiliary data structures, like lists or hash maps, are created that scale with the input size N. Therefore, the space complexity is constant, O(1).
Optimal Solution
Approach
The key insight is that the sum of a sub-array is odd only if it contains an odd number of odd numbers. Instead of recalculating sums, we just keep track of the number of sub-arrays ending at the current number with odd and even sums.
Here's how the algorithm would work step-by-step:
- Keep track of how many sub-arrays we've seen so far have an even sum and how many have an odd sum.
- When we see a new number, figure out if it's even or odd.
- If the new number is even, every sub-array sum we could make before stays the same (even stays even, odd stays odd). So, just add the old count of even sub-arrays to our total number of even sub-arrays, and the old count of odd sub-arrays to our total number of odd sub-arrays. Note that adding the new even number to an even sub-array results in an even sub-array, and adding it to an odd sub-array results in an odd sub-array.
- If the new number is odd, every sub-array sum we could make before switches parity (even becomes odd, odd becomes even). So, we add the old count of even sub-arrays to our total number of odd sub-arrays and add the old count of odd sub-arrays to our total number of even sub-arrays. The reasoning here is adding an odd number to an even sum results in an odd sum, and adding an odd number to an odd sum results in an even sum.
- Also, when starting with each new number as the start of a sub-array, an odd number is an odd sub-array of length 1, so you would increase the total number of odd sub-arrays by one. An even number contributes nothing extra here.
- The number of sub-arrays with odd sum seen so far is the final answer.
Code Implementation
def number_of_subarrays_with_odd_sum(array_of_numbers):
even_subarray_count = 0
odd_subarray_count = 0
total_odd_subarrays = 0
modulo = 10**9 + 7
for number in array_of_numbers:
if number % 2 == 0:
# Even number: parity stays the same
even_subarray_count = (even_subarray_count + 1) % modulo
else:
# Odd number: parity switches
new_even_count = odd_subarray_count
new_odd_count = (even_subarray_count + 1) % modulo
even_subarray_count = new_even_count
odd_subarray_count = new_odd_count
# Update total count of odd sub-arrays
total_odd_subarrays = (total_odd_subarrays + odd_subarray_count) % modulo
return total_odd_subarraysBig(O) Analysis
Time Complexity
O(n) – The algorithm iterates through the input array of size n exactly once. Inside the loop, it performs a constant number of operations: checking if a number is even or odd and updating the counts of even and odd sub-arrays. Therefore, the time complexity is directly proportional to the size of the input array, resulting in O(n) time complexity.
Space Complexity
O(1) – The solution uses a fixed number of variables to keep track of the counts of even and odd sum subarrays. Specifically, it maintains counters for even and odd subarray sums. The number of these counters does not depend on the size of the input array (N), so the space used remains constant regardless of N.
Edge Cases
| Case | How to Handle |
|---|---|
| Empty input array | Return 0 since there are no sub-arrays. |
| Array with a single element that is even | Return 0, since the sum will always be even. |
| Array with a single element that is odd | Return 1, since the sub-array [element] has an odd sum. |
| Array containing only even numbers | Return 0, since all sub-arrays will have even sums. |
| Array containing only odd numbers | Calculate number of sub-arrays with odd length, as only those will have an odd sum and apply modulo. |
| Array with mixed positive and negative numbers | The algorithm should correctly handle negative numbers since sum can decrease as well as increase. |
| Array with large numbers that may cause integer overflow when calculating sum | Apply modulo after each sum calculation to prevent integer overflow. |
| Very large input array | The algorithm should be O(n) to avoid time limit exceeded errors for large arrays. |
Empty input array
How to Handle:
Return 0 since there are no sub-arrays.
Array with a single element that is even
How to Handle:
Return 0, since the sum will always be even.
Array with a single element that is odd
How to Handle:
Return 1, since the sub-array [element] has an odd sum.
Array containing only even numbers
How to Handle:
Return 0, since all sub-arrays will have even sums.
Array containing only odd numbers
How to Handle:
Calculate number of sub-arrays with odd length, as only those will have an odd sum and apply modulo.
Array with mixed positive and negative numbers
How to Handle:
The algorithm should correctly handle negative numbers since sum can decrease as well as increase.
Array with large numbers that may cause integer overflow when calculating sum
How to Handle:
Apply modulo after each sum calculation to prevent integer overflow.
Very large input array
How to Handle:
The algorithm should be O(n) to avoid time limit exceeded errors for large arrays.
0/1037 Bloomberg LP questions completed
0/1037 completed
Explore Interview QuestionsTaro 75Google Interview QuestionsMeta Interview QuestionsAmazon Interview QuestionsApple Interview QuestionsNetflix Interview Questions
Explore Interview ExperiencesOpenAI Interview ExperiencesAnthropic Interview ExperiencesPerplexity Interview ExperiencesWindsurf Interview ExperiencesMistral AI Interview Experiences
