ON_OFF-EDITORIAL

PROBLEM LINK:

Contest
Practice

Setter: kulyash
Testers: iceknight1093 , jeevanjyot
Editorialist: kiran8268

DIFFICULTY:

977

PREREQUISITES:

None

PROBLEM:

Kulyash stays in room that has a single bulb and N buttons. The bulb is initially on. The initial states of the buttons are stored in a binary string S of length N, where S_i is the i the button. If Kulyash toggles any single button then the state of the bulb reverses i.e. the bulb lights up if it was off and vice versa. Kulyash has toggled some buttons and the final states of the buttons are stored in another binary string R of length N . We need to find the final stage of the bulb.

EXPLANATION:

The important things note before we beigin are:

  • The initial state of the bulb is On.
  • Even If a button is toggled the state of bulb reverses. Also, the state of bulb reverses for every single toggle.
  • Initial state of buttons are defined in string S.
  • Final state of buttons are defined in string R.


-If a single button is toggled the final state of the bulb will be 0, as the initial state is 1.
-If two buttons are toggled then the state of bulb reverses twice and stays as 1.

-Thus we can conclude that if number of buttons toggled is an even number then the state of bulb stays as 1 else if its an odd number, its state stays as 0.

TIME COMPLEXITY:

Time complexity is O(n).

SOLUTION:

Editorialist's Solution
int t;
	cin>>t;
	while(t--)
	{
	    int n,c=0;
	    string s,r;
	    cin>>n;
	    cin>>s>>r;
	  
	    
	    for(int j=0;j<n;j++)
	    {
	        if(s[j]!=r[j])
	        c++;
	    }
	    

	   if(c%2==0)
	    cout<<"1"<<"\n";
	    else
	    cout<<"0"<<"\n";

1 Like