Problem: BitFlipper

URL:

http://www.topcoder.com/tc?module=Static&d1=help&d2=sampleProblems

Problem Statement:

Binary strings, as most of us know, are composed solely of 0's and 1's. Sometimes it is necessary to turn all the bits either on (1) or off (0). However, sometimes it is not possible to just pick and flip individual bits. In this hypothetical scenario, it is only possible to flip bits in a contiguous segment which is a subset of the contiguous segment which was flipped immediately prior to it. For example, if bits 2-4 are flipped, it is not legal to flip bits 3-5 next, or bits 1-3. However, bits 3-4 or bits 2-3 would be legal. The first segment to be flipped can be located anywhere in the sequence.

Create a class BitFlipper which contains a method minFlip which determines the minimum number of bits that must be flipped under the above restriction in order to get all the bits set to 0. For purposes of this problem, to flip a bit means to change it from 0 to 1 or from 1 to 0.

DEFINITION

Class: BitFlipper
Method: minFlip
Parameters: String
Returns: int

Method signature (be sure it is declared public): int minFlip (String bits);

TopCoder will ensure the validity of the inputs. Inputs are valid if all of the following criteria are met:
* bits will be between 0 and 50 characters in length, inclusive
* bits will contain only 1's and 0's.

EXAMPLES

Example 1:
bits = "00110".
By flipping bits 3-4, we get "00000". Method returns 2.

Example 2:
bits = "10110"
If we flip bits 1-4, we get "01000". Now we flip bit 2 and get "00000".
Method returns 4 + 1 = 5.

Example 3:
bits = "1001110001"
Flipping bits 1-10 yields "0110001110"
Now, flipping bits 2-9 yields "0001110000"
Again, flipping bits 4-6 yields "0000000000"
Method returns 10 + 8 + 3 = 21.

Example 4:
bits = "10001"
Method returns 8.

Example 5:
bits = "101010101"
Method returns 25.

Example 6:
bits = ""
Method returns 0.


Solution:

public class BitFlipper{

 public int minFlip (String bits){
  int flip=0;
  while (!"".equals(bits))
  {
   bits=bits.replaceAll("^[0]*","");
   bits=bits.replaceAll("[0]*$","");
   flip+=bits.length();
   StringBuffer sb = new StringBuffer();
   for (int i=0;i<bits.length();i++){
    String cur = bits.substring(i,i+1);
    if ("0".equals(cur)) {
     sb.append("1");
    } else {
     sb.append("0");
    }
   }
   bits=sb.toString();
  }
  return flip;
 }
 
 public static void main(String[] args){
  BitFlipper bf = new BitFlipper();
  System.out.println(bf.minFlip("00110"));
  System.out.println(bf.minFlip("10110"));
  System.out.println(bf.minFlip("1001110001"));
  System.out.println(bf.minFlip("10001"));
  System.out.println(bf.minFlip("101010101"));
  System.out.println(bf.minFlip(""));
 }
}