FlippingBitsDiv1 | Topcoder Archive

Problem Statement

Goose Tattarrattat has a sequence B of bits. The length of the sequence is N. Tattarrattat also has a favorite integer M which is between 1 and N, inclusive.

A sequence of N bits is called a rotator sequence if it has the following property: its prefix of length N-M is equal to its suffix of length N-M.

For example, let M=2. Consider the sequence B="10101010". Its length is N=8, so we have N-M=6. The prefix of length 6 is "101010", the suffix of length 6 is "101010". They are the same, so this B is a rotator sequence. Now consider B="11010100". For this B we compare the prefix "110101" to the suffix "010100". They differ, so this B is not a rotator sequence.

Tattarrattat wants to change her sequence B into some rotator sequence. She will produce such a sequence in a sequence of steps. In each step she can do one of the following two types of changes to the sequence:

Flip any bit (from 1 to 0 or from 0 to 1).
Flip the first k*M bits, for any positive integer k.

You are given a String[] S and the int M. Concatenate all elements of S to obtain one long String. This String will represent the sequence B: each of its characters will be either '0' or '1'. Return the minimal number of steps required to obtain some rotator sequence.

Definition

Class:: FlippingBitsDiv1
Method:: getmin
Parameters:: String[], int
Returns:: int
Method signature:: int getmin(String[] S, int M)
(be sure your method is public)

Constraints

S will contain between 1 and 6 elements, inclusive.
Each element of S will contain between 1 and 50 characters, inclusive.
Each character in each element of S will be '0' or '1'.
M will be between 1 and N, where N is the total number of characters in S.

Examples

```
{"00111000"}
```
```
1
```
```
Returns: 2
```
An optimal solution: she can flip the first 2*1 bits to obtain "11111000", and then flip the first 5*1 bits to obtain "00000000" which is a rotator sequence.
```
{"101100001101"}
```
```
3
```
```
Returns: 2
```
```
{"11111111"}
```
```
4
```
```
Returns: 0
```
```
{"1101001000"}
```
```
8
```
```
Returns: 1
```
```
{"1","10","11","100","101","110"}
```
```
5
```
```
Returns: 4
```
Don't forget to concatenate the elements of S.

{"1001011000101010001111111110111011011100110001001"}

Returns: 16

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.