[LeetCode] 1524. Number of Sub-arrays With Odd Sum (Python)

 

난이도: Medium

Problem Description

---

Given an array of integers arr, return the number of subarrays with an odd sum.

 

Since the answer can be very large, return it modulo 109 + 7.

 

 

Problem Example

---

Example 1:

Input: arr = [1,3,5]
Output: 4
Explanation: All subarrays are [[1],[1,3],[1,3,5],[3],[3,5],[5]]
All sub-arrays sum are [1,4,9,3,8,5].
Odd sums are [1,9,3,5] so the answer is 4.

Example 2:

Input: arr = [2,4,6]
Output: 0
Explanation: All subarrays are [[2],[2,4],[2,4,6],[4],[4,6],[6]]
All sub-arrays sum are [2,6,12,4,10,6].
All sub-arrays have even sum and the answer is 0.

Example 3:

Input: arr = [1,2,3,4,5,6,7]
Output: 16

 

Constraints

---

• 1 <= arr.length <= 105
• 1 <= arr[i] <= 100

 

✏️ Solution

---

class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        answer = 0
        mod = 10**9 + 7
        odd_count, even_count = 0, 1

        prefix_sum = 0
        for num in arr:
            prefix_sum += num

            if prefix_sum % 2 == 0:
                answer += odd_count
                even_count += 1
            else:
                answer += even_count
                odd_count += 1

        return answer % mod

 

 

처음에는 먼저 arr의 prefix_sum을 구하고 brute force 방식으로 접근했는데 TLE가 발생했다..

 

O(n^2)의 시간복잡도를 가져 그러는 것 같아서 어떻게 하면 시간복잡도를 줄일 수 있을까 고민을 하다가 이전에 나온 누적합의 짝수 갯수와 홀수 갯수를 저장해놓으면 O(n)의 시간복잡도로 되지 않을까 였다.

 

새로운 누적합이 홀수라면 지금까지 짝수 누적합 개수만큼 부분 배열이 홀수가 되고, 새로운 누적합이 짝수라면 지금까지 홀수 누적합 개수만큼 부분 배열이 홀수가 되기 때문이다.

 

따라서, 이를 그대로 구현했고 정답을 맞출 수 있었다.

 

---

 

TLE가 발생한 코드는 다음과 같다..

 

class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:

        n = len(arr)
        dp = [0] * n
        answer = 0
        mod = 10**9 + 7

        for i in range(n):
            if i == 0:
                dp[i] = arr[i]
            else:
                dp[i] = (dp[i-1] + arr[i])

            if dp[i] % 2 != 0:
                answer += 1

        for i in range(1, n):
            for j in range(i, n):
                odd_sum = 0
                odd_sum = (dp[j] - dp[i-1])
                
                if odd_sum %2 != 0:
                    answer += 1

        return answer % mod

 

⚙️ Runtime & Memory

---

 

 

---

문제: 1524. Number of Sub-arrays With Odd Sum

 

깃허브: github

algorithmPractice/LeetCode/1631-number-of-sub-arrays-with-odd-sum at main · laewonJeong/algorithmPractice