PROBLEM LINK:
Author: Suthirth V
Tester: Suthirth V
Editorialist: Suthirth V
DIFFICULTY:
EASY
PREREQUISITES:
None.
PROBLEM:
Nitish was studying about how neurons interact with each other in the brain and how turning off neurons affect the overall function. He came up with a concept of “Sritz Neuron Sequence” or SNS. A neuron is a functional unit of a network and can be turned ‘On’ or ‘Off’ and can be toggled as required. A “Sritz Neuron Sequence” is one where all the “Off” neurons appear before the “On” neurons in the sequence, if they are present
Now he has been given a neuron sequence from his colleague and he wants to convert it to a SNS. At any instant, he can toggle any one neuron in the sequence from On to Off or vice versa. Your task is to find out the minimum number of toggles to achieve the goal of SNS.
QUICK EXPLANATION:
We can iterate over the number of ‘Off’ neurons in the final sequence and find the number of toggles required to achieve that configuration
EXPLANATION:
Let S be the input string. Let N be the length of S. Let us assume the characters of the string are indexed from 0 to N−1. So, if S = “ONO”, then N=3, S[0] = ‘O’, S[1] = ‘N’ and S[2] = ‘O’.
‘O’ denotes ‘Off’ and ‘N’ represents ‘On’.
Let R be the string obtained from S after performing some toggles such that in R, all ‘O’ characters occur before ‘N’. Let us consider the count of ‘O’ in R after toggling some neurons. It can be anything between 0 to N.
If the count of ‘O’ is P, then R[i] = ‘O’ for i in [0,P) and R[i] = ‘N’ for i in [P,N)
So, if we fix the count of ‘O’ to be P, then for all index i where S[i] not equal to R[i], we’ll require one toggle. So, the number of toggles required is number of index i such that i in [0,P) and S[i] = ‘N’ or i in (P,N] and S[i] = ‘O’. We can iterate over P=0 to P=N and find the number of toggles required for each P. The minimum among all will be answer. You can refer to the following pseudo code.
ans = INFINITY
for P = 0 to N
count = 0
for i = 0 to P - 1
if S[i] == ‘N’ count = count + 1
endfor
for i = P to N - 1
if S[i] == ‘O’ count = count + 1
endfor
ans = min(ans, count)
endfor
The time complexity of this solution is O(N2) for each test case.
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.