Problem Statement

You are given a String toSort containing only '0's and '1's. Using only exchange operations, we must sort this string so every '0' comes before every '1'. Return the minimal number of exchanges necessary.

Definition

Class:              Sort01
Method:             shortest
Parameters:         String
Returns:            int
Method signature:   int shortest(String toSort)
(be sure your method is public)

Notes

You can exchange any two characters in the string, not just adjacent ones.

Constraints

• toSort will contain between 1 and 50 characters, inclusive.
• Every character in toSort will be '0' (zero) or '1' (one).

Examples

0)

"010"
Returns: 1
The string can be sorted in one swap, exchanging the second and third characters.
1)

"1100"
Returns: 2

2)

"00001"
Returns: 0

3)

"10000"
Returns: 1

4)

"1101010001"
Returns: 3

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)2003, TopCoder, Inc. All rights reserved.

Google India Code Jam 2006 - Table of Contents

1. Main Page - Google India Code Jam 2006
2. Qualification Round
   • Set 1,10,13,16,25,28 :: Problem 250: ExamQuestions; Problem 1000: UnNestable
   • Set 2,9,15,20,21,27 :: Problem 250: GeneralElection; Problem 1000: UnNestable
   • Set 3,8,11,19,23,26 :: Problem 250: Sort01; Problem 1000: UnNestable
   • Set 4,7,14,18,22,29 :: Problem 250: PatternFiller; Problem 1000: PerfectNumbers
   • Set 5,6,12,17,24,30 :: Problem 250: TowerLifts; Problem 1000: PerfectNumbers
3. Elimination Round
   • Problem 250: MatrixConstructor
   • Problem 500: PalindromesAnalyzer
   • Problem 1000: VectorSet
4. Championship Round
   • Day 1, Take off to Bangalore, India (April 6, 2006)
   • Day 2, Code Jam Contest (April 7, 2006)
     • Breakfast and Google Tech Talk 1
     • The Contest Begins!!
       • Problem 300: InverseLca
       • Problem 500: ColoredDominoes
       • Problem 1000: InterestingString
     • Le Meridien and Google Tech Talk 2
     • Awards Winner announcements
     • Google Tech Talk 2 (continued) and dinner
   • Day 3, Interview with Google (April 8, 2006)
5. Links/Blogs/News