Number Of Sub Arrays With Odd Sum - Leetcode Solution

Problem:

Given an array of integers nums, return the number of subarrays with an odd sum.

A subarray is a contiguous sequence of values within an array.

Example 1:

Input: nums = [1,3,5] Output: 4 Explanation: The subarrays with an odd sum are [1], [1,3], [1,3,5], [3], [3,5], and [5].

Example 2:

Input: nums = [2,4,6] Output: 0 Explanation: There are no subarrays with an odd sum.

Example 3:

Input: nums = [1,2,3,4,5,6,7] Output: 16

Solution:

To find the number of subarrays with an odd sum, we iterate through all possible subarrays of the input array and keep a count of the number of subarrays with an odd sum.

For each subarray, we calculate its sum and check if it is odd or not. If it is odd, we increment the count.

To generate all possible subarrays of the array efficiently, we use two pointers. We initialize two pointers, left and right, to the start of the array. We then iterate through the array, moving the right pointer one element at a time.

We maintain a running sum of the values in the subarray between the left and right pointers. If this sum is odd, we increment the count of subarrays with an odd sum.

If the sum is even, we move the left pointer one element to the right. This has the effect of excluding the leftmost element of the subarray from the running sum, making it more likely that the sum will become odd.

We continue this process until we reach the end of the array, at which point we have counted all subarrays with an odd sum.

The time complexity of this solution is O(n^2), where n is the length of the input array. This is because we need to iterate through all possible subarrays of the input array.

The space complexity of this solution is O(1), as we only need to maintain a constant number of variables.

Code:

Here is the Python code for the solution:

def numSubarraysWithOddSum(nums): count = 0 for i in range(len(nums)): sum = 0 for j in range(i, len(nums)): sum += nums[j] if sum % 2 == 1: count += 1 return count

You can also solve the problem with a more optimized solution, using prefix sum to count the even and odd numbers.

1