CODEWITHSUNDEEP
arraysalgorithm
Manish Sharma
Manish Sharma

Reputation: 31

count number of subarrays with odd sum

Input : arr[] = {5, 4, 4, 5, 1, 3} 
Output : 12

Below is O(n^2) method by generating all the subarrays:-

These are possible subarrays with odd sum. 
1) {5} Sum = 5 (At index 0)
2) {5, 4}  Sum = 9
3) {5, 4, 4}  Sum = 13 
4) {5, 4, 4, 5, 1} Sum = 19
5) {4, 4, 5}  Sum = 13
6) {4, 4, 5, 1, 3}  Sum = 17
7) {4, 5}  Sum = 9 
8) {4, 5, 1, 3} Sum = 13
9) {5}  Sum = 5 (At index 3)
10) {5, 1, 3}  Sum = 9
11)  {1} Sum = 1
12) {3} Sum = 3

But how to solve this in O(n)?

Upvotes: 0

Views: 3337

Answers (1)

Selindek
Selindek

Reputation: 3423

Here is a simple solution in JAVA:

public class Odd {
  static int[] arr = { 5, 4, 4, 5, 1, 3 };

  public static void main(String... args) {
    int odd = 0;
    int even = 0;
    int result = 0;
    for (int i : arr) {
      if (i % 2 == 0) {
        even++;
      } else {
        int temp = even;
        even = odd;
        odd = temp + 1;
      }
      result += odd;
    }
    System.out.println(result);
  }

}

Here is the logic behind it:

We are going through all the elements of the array (that's why it will be O(n) ). We have 3 helper variables. Result contains the number of all the counted sub-arrays. Odd ad even contains the odd/even subarrays which ends at the current position.

Each time we process the next element we increase the subarray-count by the array which could start at the given position.

So if the current element is an odd number we increase the odd counter otherwise the even counter.

Also if the current element is odd then we have to swap the number of odd/even counters because if we add the current - odd - number to a subbarray then it will change its parity.

And finally, add the number of current odd subarrays to the result variable - actually counting the odd subarrays which end at the current position.

Upvotes: 4

Related Questions