TopCoder problem "SwitchingBits" used in TCHS SRM 10 (Division I Level Three)



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:

  1. Invert the entire string: 0001100 -> 1110011.
  2. 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:

  1. 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

0)
    
{"0001100"}
Returns: 1
Invert the two ones in the middle.
1)
    
{"11111"}
Returns: 0
Already all ones.
2)
    
{"00000001"}
Returns: 1
There are two possibilities here: invert the one, or invert all the zeroes. Either way, only 1 operation is needed.
3)
    
{"1100110011001100","000","1"}
Returns: 4
4)
    
{"11","101","101"}
Returns: 2
There are several ways. For example: 11101101 -> 11110011 -> 11111111 or 11101101 -> 11111101 -> 11111111

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=5991

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10062&pm=5991

Writer:

gevak

Testers:

PabloGilberto , brett1479 , Olexiy

Problem categories:

Greedy