Minimize cost to convert all 1s to -1s in a binary array

help
1

You are given a binary array A of size n. The frequency of 1s in the array is never greater than ⌊N/2⌋ and the remaining positions are filled with 0s.

The task is to convert all 1s to -1. We can convert 1 to -1 by pairing an existing 0 from the array with the 1. After this operation, the existing 1 and 0 both become -1. The cost of pairing two elements at index i and j is abs(i-j).

Minimize the cost of converting all 1s to -1.

Note: We have to convert all 1s to -1, not necessarily all the 0s. So, if at any point, all 1s have been converted to -1 but there are still 0s in the array, the task is considered completed.

Constraints: 2 <= N <= 4000

2

@ronith1 The following program compares recursive greedy algorithm to recursive brute-force algorithm, and passes exhaustive test for all possible binary arrays of size up to N = 17, where the number of ones is at most equal to the number of zeros. However, the greedy algorithm does not seem to be fast enough to handle arrays with larger values of N.

Exhaustive test

Hope that this code helps you in finding faster solution.