SWITCHES - Editorial

PROBLEM LINK:

https://www.codechef.com/RSC2017/problems/SWITCHES

Author: spraveenkumar

DIFFICULTY:

SIMPLE

PREREQUISITES:

Greedy

PROBLEM:

You are given a binary string stating the state of n switches. You need to calculate the minimum number of toggles to make to bring every switch to ON state. There is one special switch that inverts the state of every other switch which can be used.

QUICK EXPLANATION:

So the target state is every switch is ON in minimum toggles. When there is more number of ONs, it is pointless to use the special switch to invert them. But when number of OFF switches are more, they all can be made active in 1 toggle. So the answer is min(no of OFF,no of ON+1);

EXPLANATION:

The solution to this problem lies in counting the number of switches that are ON and OFF. If less number of switches are OFF, it can be toggled ON in less number of toggles. But if it was the other way round, then the all the switches that are ON can be toggled OFF and then the special switch can be used. So we first count the number of 0s and 1s(ONs and OFFs). Then if the OFFs are less, then the number of OFFs is the number of toggles we make and hence the answer. If the number of ONs are less, then that plus 1 is the answer(where 1 is added for the special switch). So the answer is min(no of OFFs,no of ONs+1)

AUTHOR’s SOLUTION:

import java.util.Scanner;
class Switches{
    public static void main(String args[]){
	 Scanner sc = new Scanner(System.in);
	 int t = sc.nextInt();
	 while(t-- != 0){
	    String s = sc.next();
	    int[] c = new int[2];
	    for(int i = 0; i < s.length(); i++){
		c[s.charAt(i)-'0']++;
	    }
	    System.out.println(c[0]<c[1]+1?c[0]:c[1]+1);
	 }
	 sc.close();
    }
}