Today I have done leetcode's February LeetCoding Challenge with cpp.

February LeetCoding Challenge 25

Description

Number of Sub-arrays With Odd Sum

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

Solution

class Solution {
  const int MOD = 1e9 + 7;
public:
  int numOfSubarrays(vector<int>& arr) {
    for(auto &n : arr) {
      n ^= (n ^ (n & 1));
    }
    for(int i = 1; i < arr.size(); ++i) {
      arr[i] ^= arr[i - 1];
    }
    int ones = 0;
    int zeros = 1;
    int answer = 0;
    for(auto n : arr) {
      if(n) {
        answer += zeros;
        ones += 1;
      } else {
        answer += ones;
        zeros += 1;
      }
      answer %= MOD;
    }
    return answer;
  }
};

// Accepted
// 151/151 cases passed (2 ms)
// Your runtime beats 76.78 % of cpp submissions
// Your memory usage beats 55.17 % of cpp submissions (112 MB)