## Number of Sub-arrays With Odd Sum

### Challenge

Givin an array, return the number of odd-sum of sub arrays.

For more explanation see leetcode challenge.

### My approaches

1. First
``````    def numOfSubarrays(self, arr: List[int]) -> int:
subs = [
sum( arr[ i : j+1 ] )
for i, _ in enumerate(arr)
for j in range( i, len(arr) )
if sum( arr[ i : j+1 ] ) % 2 != 0
]
ans = len(subs) % (10**9 + 7)
return ans
``````

This catches TLE(Time Limit Error) on 79th test case out of 151.

1. Second
``````    def numOfSubarrays(self, arr: List[int]) -> int:
lng = len(arr)

subs = (
sum( arr[ i : j+1 ] )
for i, _ in enumerate(arr)
for j in range( i, lng )
)

odds = list( filter( lambda it: it % 2 != 0, subs)  )

ans = len(odds) % (10**9 + 7)
return ans
``````

A little faster, but still fails at test case 82 as TLE.

1. Third
``````    def numOfSubarrays(self, arr: List[int]) -> int:
count = 0
lng = len(arr)
for i in range(lng):
pv = None
for j in range( i, lng ):

if pv is None:
pv = arr[i]
if pv % 2 != 0: count += 1
continue

cur = pv + arr[j]

if cur % 2 != 0: count += 1

pv = cur

cst = 10**9 + 7

return count % cst
``````

There much progress here in speed-wise since it passed test cases upto 115, not included, but still failed with TLE.

### Others' much faster approaches

However I did, it doesn't seem to allow me to pass because the time complexity of my alogorithms is `O(n^2)` because I used two for loops.

Other coding gurus however used only single for loop to solve this. They used CS concepts like dynamic programming, prefix sum, binary bitwise operation(XOR)

Here are some codes derived from others.

``````class Solution:
def numOfSubarrays(self, arr: List[int]) -> int:
counts = [1, 0]
cur = 0
for a in arr:
cur ^= a % 2
counts[cur] += 1
return counts * counts % (10**9 + 7)
``````
``````class Solution:
def numOfSubarrays(self, A: List[int]) -> int:
mod = 10 ** 9 + 7
n = len(A)
preSum = [0, A]
for i in range(1,n):
preSum.append(preSum[-1] + A[i])

even = 0
odd = 0

for i in preSum:
if i%2 == 0:
even += 1
else:
odd += 1

return (odd*even)%mod
``````
``````class Solution:
def numOfSubarrays(self, arr: List[int]) -> int:
e=0
o=0
s=0
ans=0
for i in arr:
s=s+i
if s%2==0:
ans+=o
e+=1
else:
ans=ans+1+e
o+=1
ans=ans%((10**9)+7)
return ans
``````
``````class Solution(object):
def numOfSubarrays(self, arr):
"""
:type arr: List[int]
:rtype: int
"""

ret = 0
odd_count, even_count = 0, 0

for num in arr:
if num % 2 != 0:
ret += even_count + 1
odd_count, even_count = even_count + 1, odd_count
else:
ret += odd_count
odd_count, even_count = odd_count, even_count + 1

return ret % (10 ** 9 + 7)
``````
``````class Solution:
def numOfSubarrays(self, arr: List[int]) -> int:
res = odd = even = 0
for x in arr:
even += 1
if x % 2:
odd, even = even, odd
res = (res + odd) % 1000000007
return res
``````

#### Key takeaway

Honestly I still don't fully get it. But I learnt new concepts like bitwise operation, dynamic programming, prefix sum etc., and I know that such things can help reduce time complexity tremendously.

codingchallenge leetcode python