Sub-Arrays With Odd Sum

Easy
0/40
Average time to solve is 20m
profile
Contributed by
4 upvotes
Asked in companies
AmazonSnapdeal Ltd.Spinny

Problem statement

You are given an array ‘ARR’ of size ‘N’. Your task is to find the total number of sub-arrays with an odd sum. The sub-array is a contiguous part of an array. For example, consider the array [1, 2, 3], There are 6 non-empty sub-arrays. The sub-arrays are [1], [2], [3], [1,2], [2,3] and [1,2,3].

Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line of the input contains an integer, 'T,’ denoting the number of test cases.

The first line of each test case contains a single integer, 'N', denoting the number of elements in the array.

The second line of each test case contains 'N' space-separated integers denoting the elements of the array 'ARR'.
Output Format: 
For each test case, print a single integer - the total number of sub-arrays with an odd sum. 

Print the output of each test case in a separate line.
Note: 
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints: 
1 <=  T <= 10
1 <=  N <= 10^5
1 <=  ARR[i] <= 10^4

Where 'T' denotes the number of test cases, 'N' denotes the number of elements in the array, and 'ARR[i]' denotes the 'i'th' element of the array 'ARR'.

Time limit: 1 sec
Sample Input 1:
2
3    
2 1 2
4
1 2 2 3
Sample Output 1:
4
6
Explanation For Sample Input 1:
For the first test case, 
All possible sub-arrays with odd sum are [1] , [2,1] , [1,2] and [2,1,2]. Hence, the answer is 4 in this case.

For the second test case,
All possible sub-arrays with odd sum are [1] , [3] , [1,2] , [2,3] , [1,2,2] and [2,2,3]. Hence, the answer is 6 in this case.
Sample Input 2:
2
5 
1 2 1 2 1 
4 
1 3 5 5
Sample Output 2:
9
6
Explanation For Sample Input 2:
For the first test case, there are total 9 combinations of sub-arrays with an odd sum. . Hence, the answer is 9 in this case.

For the second test case, there are total 6 combinations of sub-arrays with an odd sum. Hence, the answer is 6 in this case.
Hint

Check for each sub-array whether the sum of all elements in the sub-array is odd or not.

Approaches (3)
Brute Force

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
Time Complexity

O(N^3), where N is the number of elements in the array.

 

We are doing N iterations, and in each iteration, it takes O(N^2) time to find the total number of sub-arrays with an odd sum. Hence the overall time complexity is O(N^3).

Space Complexity

O(1).

 

Constant space is being used. Hence, the overall Space Complexity is O(1).

Code Solution
(100% EXP penalty)
Sub-Arrays With Odd Sum
Full screen
Console