Skip to content

Latest commit

 

History

History
98 lines (79 loc) · 2.89 KB

_1524. Number of Sub-arrays With Odd Sum.md

File metadata and controls

98 lines (79 loc) · 2.89 KB

1524. Number of Sub-arrays With Odd Sum

All prompts are owned by LeetCode. To view the prompt, click the title link above.

Back to top

First completed : February 26, 2025

Last updated : February 26, 2025

Related Topics : Array, Math, Dynamic Programming, Prefix Sum

Acceptance Rate : 56.12 %

V0

Initial attempt where I make each iteration by pass and reuse the existing array. Was inefficient I realized but the math worked. The process consisted of...

  1. Turning arr into a prefix sum array
  2. Replacing each index of arr with a tuple containing the prefix count of the number of items prior that had an odd or even prefix sum
  3. Returning the number of odd prefix sums plus the number of odds times the number of evens (since those can be matched up to get a subarray).

V1

Much improved version that insteads sums the cases during the odds and evens iteration rather than replacing the array values

V2

Improved version off of V1 that removes the need for the first prefix sum pass as it does all calculations within a single pass.

Solutions

Python

m1524 v0.py

class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        for i in range(1, len(arr)) :
            arr[i] += arr[i - 1]

        arr[0] = (arr[0] % 2, (arr[0] + 1) % 2)     # (# odds, # evens)
        for i in range(1, len(arr)) :
            arr[i] = (arr[i - 1][0] + arr[i] % 2, arr[i - 1][1] + (arr[i] + 1) % 2)

        return arr[-1][0] + arr[-1][1] * arr[-1][0] % (10 ** 9 + 7)

m1524 v1.py

class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        for i in range(1, len(arr)) :
            arr[i] += arr[i - 1]

        output = 0
        evens, odds = 1, 0
        for i in range(len(arr)) :
            if arr[i] % 2 : # odd
                output += evens
                odds += 1
            else :
                output += odds
                evens += 1
        return output % (10 ** 9 + 7)

m1524 v2.py

class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        output = 0
        pref_sum = 0
        evens, odds = 1, 0
        for num in arr :
            pref_sum += num
            if pref_sum % 2 : # odd
                output += evens
                odds += 1
            else :
                output += odds
                evens += 1
        return output % (10 ** 9 + 7)