Sub-Arrays With Odd Sum

The approach to this problem will be to check for each sub-array, if the sum of all elements in the sub-array is odd or not. We will use the modulo operator to find the remainder produced when the sum of all sub-array elements is divided by 2. If the remainder is 1, then the sum of all sub-array elements is odd.

Algorithm:

1. We will initialize the variable TOTALSUBARRAYS with 0, and it will store the total number of sub-arrays with an odd sum.
2. iterate START from 0 to N - 1,
   • iterate END from START  to N - 1
     • We will set variable TOTALSUM as 0, which stores the total sum of the sub-array from START to END
     • Iterate POS from START to END
       • Increment TOTALSUM by ARR[POS] 
     • If TOTALSUM is odd, then increment TOTALSUBARRAYS by 1.
3. Return the variable TOTALSUBARRAYS

You can find the sum of all elements in the subarray from start to end index in the below way:

ARR[start : end] = ARR[0 : end] - ARR[0: start - 1]

Therefore, our approach will be to maintain an array PREFIXSUM of size N to store the prefix sum of the array. We will set the variable TOTALSUBARRAYS as 0, which stores the total number of sub-arrays with an odd sum. We will iterate start from 0 to N - 1, and we will find PREFIXSUM[START], which is equal to PREFIXSUM[START - 1] + ARR[START]. 

Now there will be two cases:

1. If PREFIXSUM[START] is odd, we will iterate POS from 0 to START - 1, and we will check if PREFIXSUM[START] - PREFIXSUM[POS] is odd, then we will increment TOTALSUBARRAYS by 1. We will increment TOTALSUBARRAYS by 1 to include the sub-array from 0 to START.
2. If PREFIXSUM[START] is even, we will iterate POS from 0 to START - 1, and we will check if PREFIXSUM[START] - PREFIXSUM[POS] is odd, then we will increment TOTALSUBARRAYS by 1.

Algorithm:

1. We will set the variable TOTALSUBARRAYS as 0. The variable TOTALSUBARRAYS stores the total number of sub-arrays with an odd sum.
2. Maintain an array PREFIXSUM of size N to maintain the prefix sum of the array.
3. Iterate START from 0 to N - 1,
   • If START is equal to 0, then assign PREFIXSUM[0] with ARR[0], otherwise assign PREFIXSUM[START] with PREFIXSUM[START - 1] + ARR[START]. 
   • Check if PREFIXSUM[START] is odd, then increment TOTALSUBARRAYS by 1 to include subarray from 0 to START and iterate POS from 0 to START
     • If PREFIXSUM[pos] is even, then increment TOTALSUBARRAYS by 1
   • if PREFIXSUM[START] is even, then iterate POS from 0 to START
     • If prefixPREFIXSUMum[POS] is odd, then increment TOTALSUBARRAYS by 1
4. Return the variable TOTALSUBARRAYS.

The intuition behind the approach is to observe that the difference between odd and even numbers is an odd number. Similarly, the difference between even and odd numbers is an odd number. You can find the sum of all elements in the subarray from start to end index in the below way:

ARR[start : end] = ARR[0 : end] - ARR[0: start - 1]

If ARR[0 : END]  is odd, then we need to find ARR[0: START - 1] with even values to obtain ARR[START : END],i.e sum of sub-array from start to end, with odd values. Similarly, If ARR[0 : END]  is even, then we need to find ARR[0: START - 1] with odd values to obtain ARR[START : END] with odd values.

Therefore, our approach is to keep track of the total number of the prefix with odd and even sum. We will maintain two variables, EVENPRESUM, and ODDPRESUM, which stores the total number of the prefixes of the array with even and odd sum respectively and we will set both variables as 0. We will set the variable TOTALSUBARRAYS as 0, which stores the total number of sub-arrays with an odd sum. We will iterate START through 0 to N - 1 and find the sum of all elements in the array from 0 to START. Let the obtained value be CURRPRESUM.

Now there will be two cases:

1. If CURRPRESUM is odd, we need to find the total number of the prefix with even sum till START to obtain the total number of sub-arrays with odd sum ending at START, that is equal to EVENPRESUM. We will increment TOTALSUBARRAYS by EVENPRESUM + 1 and ODDPRESUM by 1. We are increasing TOTALSUBARRAYS by an extra 1 to include the sub-array from 0 to START.
2. If CURRPRESUM is even, we need to find the total number of the prefix with odd sum till START to obtain the total number of sub-arrays with odd sum ending at START, that is equal to ODDPRESUM. We will increment TOTALSUBARRAYS by ODDPRESUM and EVENPRESUM by 1.

Algorithm:

1. We will set the variable TOTALSUBARRAYS as 0, the variable evenPreSum as 0, ODDPRESUM as 0 and CURRPRESUM as 0. The variable TOTALSUBARRAYS stores the total number of sub-arrays with an odd sum. The two variables evenPreSum and ODDPRESUM store the total number of odd and even prefix sum of the array. The variable CURRPRESUM stores the current prefix sum of the array.
2. Iterate START from 0 to N - 1,
   • Increment CURRPRESUM by ARR[START] to obtain the sum of all sub-array elements from 0 to START(Both inclusive).
   • If CURRPRESUM is odd, then increment TOTALSUBARRAYS by EVENPRESUM + 1 and ODDPRESUM by 1. Otherwise, increment TOTALSUBARRAYS by ODDPRESUM and EVENPRESUM by 1. Note that when the sum is odd, we increase TOTALSUBARRAYS by an extra 1 to include the sub-array from 0 to START.
3. Return the variable TOTALSUBARRAYS