Introduction

In this blog post, we will explore how to solve the LeetCode problem "1524" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like Chatmagic, we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

Problem Statement

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. 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

Explanation

Here's a breakdown of the solution:

• Key Idea: Instead of calculating the sum of every subarray, we can maintain counts of subarrays ending at the current index with even and odd sums.
• Dynamic Programming: We iterate through the array, updating the even and odd counts based on whether the current element is even or odd.

• Modulo Arithmetic: We apply the modulo operator at each step to prevent integer overflow.

• Complexity: Time: O(n), Space: O(1)

Code

    def numOfSubarrays(arr):
    """
    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.
    """
    MOD = 10**9 + 7
    even_count = 0
    odd_count = 0
    result = 0

    for num in arr:
        if num % 2 == 0:
            even_count += 1
        else:
            new_even_count = odd_count
            new_odd_count = even_count + 1
            even_count = new_even_count
            odd_count = new_odd_count

        result = (result + odd_count) % MOD

    return result