Longest subarray with equal parity after k or less operations

user_9489702 0
Viewed 402

I recently came across a coding question in a contest and I'm unable to figure out a way to solve this. (I'm out of the contest :) )

So here is the question: Consider an array of integers where each element can be modified by two operations. Either divide the element by 2 or multiply the element by 2.

Given k chances to modify the elements of the array by above mentioned operations (each time an element is modified is considered as one operation) ,find out the maximum length contiguous sub array such that all the elements in the sub array have the same parity.

Parity - Remainder when a number is divided by 2

eg :- consider an array 12,11,10,4 and k = 1 Here the parity of the elements is 0,1,0,0. On multiplying 2nd element 11 with 2(and hence completing one operation) we can obtain a parity of 0 (As 22 leaves a remainder 0) and hence given k=1 operations, max length of a contiguous sub array with elements having same parity is 4

dynamic-programming data-structures arrays algorithm
1 Answers

This is easiest if you divide it into two subproblems: Find the longest achievable subarray with parity 0 with <= k moves, and Find the longest achievable subarray with parity 1 with <= k moves. Then pick whichever answer is longer.

Both of these subproblems are easily solved with the two pointer method. For parity 0:

  1. Assign low and high pointers to the start of array
  2. We will keep track of how many moves it takes to achieve parity 0 for the subarray between the pointers. Initialize this subarray cost to 0.
  3. Increment the high pointer. Add the cost for the new element in the subarray.
  4. While the cost > k, increment the low pointer and remove the cost of the element that is removed from the subarray.
  5. Go back to 3 until the high pointer exits the array. Remember the longest subarray seen at this step.

Note that getting a 0 to parity 1 has infinite cost. For the purpose of the above algorithm, you can say it costs k+1.

user_54835260
Related