SwitchingBits | Topcoder Archive

Problem Statement

You have a string s containing only ones and zeroes. Your goal is to make all the characters in s equal using a minimal number of operations. A single operation consists of inverting all the characters in a contiguous substring of s. Inverting a character means transforming a one into a zero, and vice versa.

For example, consider the string "0001100" (quotes for clarity). We can transform this string into all ones using 2 operations:

Invert the entire string: 0001100 -> 1110011.
Invert the substring from the 4th character to the 5th character, inclusive: 1110011 -> 1111111.

We can transform the same string into all zeros using just 1 operation:

Invert the substring from the 4th character to the 5th character, inclusive: 0001100 -> 0000000.

Thus, the answer for s="0001100" is 1.

You are given s as a String[]. Concatenate the elements of s to obtain the actual string, and return the minimal number of operations necessary to transform s into all ones or all zeroes.

Definition

Class:: SwitchingBits
Method:: minSwitches
Parameters:: String[]
Returns:: int
Method signature:: int minSwitches(String[] s)
(be sure your method is public)

Constraints

s will contain between 1 to 50 elements, inclusive.
Each element of s will contain between 1 and 50 characters, inclusive.
Each element of s will contain only ones ('1') and zeroes ('0').

Examples

```
{"0001100"}
```
```
Returns: 1
```
Invert the two ones in the middle.
```
{"11111"}
```
```
Returns: 0
```
Already all ones.
```
{"00000001"}
```
```
Returns: 1
```
There are two possibilities here: invert the one, or invert all the zeroes. Either way, only 1 operation is needed.

{"1100110011001100","000","1"}

Returns: 4

```
{"11","101","101"}
```
```
Returns: 2
```
There are several ways. For example: 11101101 -> 11110011 -> 11111111 or 11101101 -> 11111101 -> 11111111

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.