PROBLEM LINK:Author: Ashish Ahuja DIFFICULTY:SIMPLEEASY PREREQUISITES:String processing PROBLEM:The problem focuses on string manipulation,here a string of 0s and 1s. QUICK EXPLANATION:The problem poses a situation in front of the programmer to find out the most efficient algorithm for bringing together a specified number of 1s together. EXPLANATION:It is one of the simpler problems, focused for the newbie programmers. It urges a programmer to manipulate the given string of 0s and 1s in such a way all the 1s are brought together in least possible iterations, and hence in minimum possible time. The solution to the problem has been aimed to check the positioning of each character of the string. This has been done by keepin track of the characters before and after the positions where a 1 is encountered. This is shown below  for(int i = 0 ; i < median ; i++) left += position[i]; for(int i = median + 1 ; i<=m ; i++) right += position[i]; Then towards the information acquired from above is used to finally find out the minimum number of ways to bring the 1s together. for(int i = m+1 , j = 1 ; i < position.size() ;j++, i++){ left = position[j]; left += position[var_median]; var_median++; right = position[var_median]; right += position[i]; long long temp = right  left + (2median  m  1)position[var_median]; ans = min(ans , temp); } AUTHOR'S AND TESTER'S SOLUTIONS:Author's solution can be found here.
This question is marked "community wiki".
asked 24 Mar '16, 16:48
