Challenge
Givin an array, return the number of odd-sum of sub arrays.
For more explanation see leetcode challenge.
My approaches
- 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.
- 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.
- 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[0] * counts[1] % (10**9 + 7)
class Solution:
def numOfSubarrays(self, A: List[int]) -> int:
mod = 10 ** 9 + 7
n = len(A)
preSum = [0, A[0]]
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.