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.

  1. r0bertz
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)
  1. srajsonu
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
  1. Anurag_Tiwari
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
  1. galbie
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)
  1. yanrucheng
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