Odd Even Subarrays

Question

I've been trying to understand Dynamic Programming lately, here's the question I just attempted:

You are given an array A of N positive integer values. A subarray of this array is called an Odd-Even subarray if the number of odd integers in this subarray is equal to the number of even integers in this subarray.

Find the number of Odd-Even subarrays for the given array.

Solving this on hackerearth, here!

I immediately connected this with Matrix-Chain Multiplication from CLRS, which tries all sub-arrays. To optimise it for this question, I used the numEvens array to track number of even ints from index 0 to i. This takes \$O(n)\$ time. This way I don't have to actually scan every sub-array to see if it's Odd-Even or not. evensIJ tells me how many even ints are in arr[i..j]. I still have to visit every sub-array though, thus the \$O(n^2)\$ nested loops, where l is the length of the sub-array.

Here's the code, it takes as input the array arr of ints and it's size n:

long int numArrs(int arr[], int n)
{
 int numEvens[n], l, i, j, evensIJ;
 if (arr[0] & 1) numEvens[0] = 0;
 else numEvens[0] = 1;
 for (i = 1; i < n; i++)
 numEvens[i] = (arr[i] & 1) ? (numEvens[i - 1]) : (1 + numEvens[i - 1]);
 long int count = 0;
 for (l = 2; l <= n; l += 2)
 {
 if (l > n) break;
 for (i = 0; i < n - l + 1; i++)
 {
 j = i + l - 1;
 evensIJ = numEvens[j] - numEvens[i] + ((arr[i] & 1) ? 0 : 1);
 if (2*evensIJ == (j - i + 1))
 count++;
 }
 }
 return count;
}

I believe my code is correct but it give a Time Limit Exceeded error on larger test cases, even though it solves all smaller ones correctly. Any way to optimise it? Should I completely abandon this approach or should I optimise on this approach somehow?

Any style advise is also appreciated since I've been coding in Python3 for the last two years and have just shifted to C++14 last week because I need speed for competitive coding and all.

Also, side note, changing

evensIJ = numEvens[j] - numEvens[i] + ((arr[i] & 1) ? 0 : 1);

to

evensIJ = numEvens[j] - numEvens[i - 1];

makes the code incorrect. Am I being dumb for not getting why this happens?

• Martin R: "... it give a Time Limit Exceeded ..." – so this is from some programming challenge? Can you add the link to the problem description?
• Pranjal Verma: @MartinR added link to the challenge.
• juvian: check here for a O(n) solution
• Pranjal Verma: @juvian yes! thank you very much, this certainly is the best way to do it.

Answer 1

First, the code review:

long int numArrs(int arr[], int n)

With C++14, you can do better than use built-in arrays (decaying to a pointer in a function, whatever the signature says): use rather std::vector, or std::array if you know the size at compile time.

{
 int numEvens[n], l, i, j, evensIJ;

Don't declare your variables unless you're ready to define them. Wait as much as possible to keep the declaration near to where you use your variable.

 if (arr[0] & 1) numEvens[0] = 0;
 else numEvens[0] = 1;

Try not to clutter your code with useless repetitions. For instance you might write:

numEvens[0] = (arr[0] & 1) ? 0 : 1;

or

numEvens[0] = !(arr[0] & 1);

By the way, don't hesitate to declare short functions that the compiler will inline, they'll make your code clearer:

constexpr bool is_odd(int i) { return i & 1; }

 for (i = 1; i < n; i++)
 numEvens[i] = (arr[i] & 1) ? (numEvens[i - 1]) : (1 + numEvens[i - 1]);

Raw loops (for loops which don't say what they're doing) should be replaced with standard, named algorithms whenever you can. Look for instance at std::partial_sum.

 long int count = 0;
 for (l = 2; l <= n; l += 2)

try to give your variables more meaningful names, e.g : l -> length

 {
 if (l > n) break;
 for (i = 0; i < n - l + 1; i++)
 {
 j = i + l - 1;
 evensIJ = numEvens[j] - numEvens[i] + ((arr[i] & 1) ? 0 : 1);
 if (2*evensIJ == (j - i + 1))
 count++;
 }
 }
 return count;
}

This nested loop is why it's taking too much time. There's an O(n) algorithm for this, which relies on dynamic programming (your program doesn't, in my opinion).

The idea is to use a map to keep track of the imbalances you've seen; whenever you come back to an imbalance, it means that you're correcting it, and so you increase your result by the number of times you've visited it:

long int count_balanced_subarrays(const std::vector<int>& input) {
 std::map<int, int> imbalances;
 imbalances[0] = 1; // 0 is the initial position, that's why it's already marked
 unsigned odd_count = 0;
 unsigned even_count = 0;
 long int res = 0; 
 for (unsigned i = 0; i < input.size(); ++i) {
 if (input[i] & 1) ++odd_count;
 else ++even_count;
 res += imbalances[odd_count - even_count]++;
 } 
 return res;
}

• Pranjal Verma: holy damn! There's even a std::partial_sum!? C++14 is amazing lol. Thanks for the great review, I'll be sure to correct these issues moving forward. I believed storing the partial sums was a form of Dynamic Programming but the O(n) solution is certainly the best, thanks!
• Martin R: Remark: A single count variable (which is incremented or decremented) would be sufficient.
• papagaga: @MartinR: Indeed, but I wanted to make the algorithm more obvious (it isn't that intuitive)