An array of N animals, consisting only of snakes and mongooses in a particular order is given to you. Given that each mongoose can eat at most one snake immediately adjacent to it, determine whose frequency is greater given that the mongoose eat optimally so as to minimise the frequency of the snakes.
QUICK EXPLANATION -
The question is of ad - hoc and greedy type. The question states
It can be easily solved if each mongoose uses the greedy strategy of first checking if its immediate left neighbour and if not possible to eat it then check its right neighbour.
Iterate over all the mongoose from left to right and for each mongoose check if its immediate left neighbour can be eaten, if yes, then increment the answer and move to the next mongoose. Otherwise, check if its immediate right neighbour can be eaten, if yes, then increment the answer and move on.
By checking a neighbour we mean, we need to check that the particular position is occupied by a snake which is NOT eaten already.
The pseudocode will be -
bool eaten[N] int T input T FOR i = 1 to T: string S input S int snakes = 0, mongooses = 0, answer = 0 FOR j = 0 to S.length() - 1: eaten[j] = 0 FOR j = 0 to S.length() - 1: if(S[j] == 'm'): mongooses++ if(eat(j - 1)): answer++ else if(eat(j + 1)): answer++ else: snakes++ snakes -= answer if(snakes > mongooses): print "snakes" else if(mongooses > snakes): print "mongooses" else: print "tie" bool eat(int x): if(x < 0 or x >= S.length()): return false if(S[x] == 's' and eaten[x] == 0): eaten[x] = 1 return true return false
Time Complexity -
Time complexity per test case is O(N), therefore the total time complexity is O(N * T)