Number of Sub-arrays With Odd Sum - Leetcode 1524 - Python

0:00 - Understand the problem
4:10 - Drawing Explanation
8:55 - Dry Run
11:03 - Coding Explanation

leetcode 1524

#neetcode #leetcode #python

[ObtecularPk]

This is absurd. Ain't no way a normal person going through DSA would have gotten this problem.

[jotrades]

Ladies and gentleman I am happy to share that I have finally solve a problem where me and Neetcode had the same thought process

[rumonintokyo]

Goodluck getting da trick in an interview these questions are insane

[vanshsamaiya]

I always liked your solutions, I think you could have improved this video by taking a bigger array as example (just a feedback) btw love your videos

[anonMan]

Thank you neetcode youre the goat disregard haters appreciate the daily

[TechEnthusiast]

for the first time, i was not able to understand your solution, that is what you were trying to convey

[dibyajyotighosh]

Maybe this details will help you understand this better:

Even + Odd = Odd
Odd + Even = Odd

If the current cumulative SUM IS EVEN, adding an element that gives an odd sum depends on how many previous sums were odd.
If the current cumulative SUM IS ODD, adding an element that gives an odd sum depends on how many previous sums were even.

[laumatthew]

Instead of keeping track current sum, we may instead keep track of the current parity, to prevent potential overflow issue.

[AryamEzra]

Thank you. The dry run really helped help clear things up! :-)

[deadlyecho]

You don't need the curr sum, you could check the number itself it is odd or even and based on the evens and odds you could detect if you need to add evens or odds count to the result, prefix even and odd counts instead

[Mahidhar-wp]

class Solution:
def numOfSubarrays(self, arr: List[int]) -> int:
curr, odd, even = 0, 0, 1
for val in arr:
curr ^= val & 1
if curr:
odd += 1
else:
even += 1
return (even * odd) % (10**9 + 7)

[razialghul]

definitely thought of your Subarray Sum Equals K solution video when I first saw the problem

[shobhitmaste]

the C++ Code that i wrote this morning





int numOfSubarrays(vector<int>& arr) {
int MOD =
int result = 0;
int n = arr.size();
int sum = 0;
long long odd = 0;
long long even = 0;
for(int i = 0 ; i < n; i++){
sum += arr[i];
if(sum%2 == 1){
result++;
odd++;
}
else
even++;
}
cout<<odd<<" "<<even;
return (((odd * even) % MOD) + odd) % MOD;
}

edit* - the result variable is just the leftover variable from my another try at this question and forgot to remove it in the leetcode submission

[wrathop]

What is wrong with me I could feel after looking at the problem that it can be a prefix sum or a dp but couldn't come up with a solution either way.

[yaroslavyatsyk]

It is like a modified Kadane's Algorithm

[alifrahman]

intuition: two numbers of different parity sum (or subtract) to an odd number. so it would be nice if we can split subarray sums into two numbers --> turns out we can by subtracting a current prefix sum with an earlier prefix sum (i only knew this part from doing other subarray sum problems). So we need these sums to be different parities for the resultant subarray sum to be odd. Back to the algo: So as we iterate through the array, we update current prefix sum, and we look back to see if we had prefix sums with the opposite parity. suppose there are n of these prefix sums. therefore there are n pairs we can make. therefore there are n subarray sums that are odd. so we add this number to our result and move on to the next prefix sum.

[yashwantptl]

am I the only one not getting the math completely ?!

[roshank.r.]

i solved it in O(n) for both time and space. but came here for your thought process

[sumanshekhar]

I think at the end he swapped the conditions ODD with EVEN and EVEN with ODD in hurry
Anyways awesome explaination :)

[robert.baindourov]

So if its even you add all odd possibilities to the current prefix and if its odd you add 1 for itself alone, and all the even possibilities. Because odd number +an even number is odd.