UniformingArray | Topcoder Archive

Problem Statement

You are given an int[] A consisting of zeros and ones, and an odd int k. You are allowed to perform operations of the following form:

Select a contiguous subarray of A of length exactly k.
Replace all the elements in that subarray by the element that appears more often.

Recall that k is odd, so any such operation is always well defined. What is the minimum number of these operations needed to transform A to an int[] of the same length consisting of all ones? If there is no way to achieve that, output -1.

Definition

Class:: UniformingArray
Method:: minOperations
Parameters:: int[], int
Returns:: int
Method signature:: int minOperations(int[] A, int k)
(be sure your method is public)

Constraints

A will contain between 3 and 2,000 elements, inclusive.
Each element of A will be 0 or 1.
k will be odd.
k will be between 3 and |A|, inclusive.

Examples

```
{1, 0, 1}
```
```
3
```
```
Returns: 1
```
After performing an operation on the entire A, the result is {1, 1, 1}.
```
{1, 1, 1, 1}
```
```
3
```
```
Returns: 0
```
The input A already consists of all ones, so it is not needed to perform any operation.
```
{0, 0, 1, 0, 1, 0}
```
```
3
```
```
Returns: 4
```
Here is a possible sequence of operations that transforms A to an all-ones int[]. (The marks XXX represent which subarrays the operations are applied to.) 1. {0, 0, 1, 0, 1, 0} -> {0, 0, 1, 1, 1, 0} X X X 2. {0, 0, 1, 1, 1, 0} -> {0, 1, 1, 1, 1, 0} X X X 3. {0, 1, 1, 1, 1, 0} -> {0, 1, 1, 1, 1, 1} X X X 4. {0, 1, 1, 1, 1, 1} -> {1, 1, 1, 1, 1, 1} X X X

{0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0}

Returns: 6

{0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0}

Returns: 11

```
{0, 0, 1, 0, 0, 1, 0, 0, 1}
```
```
5
```
```
Returns: -1
```
It can be shown that A cannot be turned into all-ones int[] by applying any number of described operations.

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.