You’re given an array of houses some of which have a bomb and others don’t. These bombs will explode simultaneously and when bomb in ith house explodes, it destroys adjacent houses. Your task is to find out the number of houses which aren’t destroyed.
For every house check if it is destroyed or not.
There are two almost similar ways of solving this problem. Key idea is to find out for each house if it is destroyed or not. How do we check if ith house will be destroyed or not? It will be destroyed iff at least one of i-1, i and i+1th houses have a bomb. Just beware of the boundaries as first and last houses have only one adjacent house. So final solution is :
saved_count = 0 for i from 1 to N destroyed = false if( S* == '1') destroyed = true if( i > 1 and S[i-1] == '1') destroyed = true if( i < N and S[i+1] == '1') destroyed = true if( not destroyed) saved_count += 1 print saved_count
An alternative solution would be to move over houses with bombs and mark those houses that will explode.
bool will_be_destroyed [N] fill( will_be_destroyed, false) for i from 1 to N if S* == '1' will_be_destroyed* = true if(i > 1) will_be_destroyed[i-1] = true if(i < N) will_be_destroyed[i+1] = true saved_count = 0 for i from 1 to N if(not will_be_destroyed*) saved_count += 1 print saved_count
Both of these are O(N) solutions and very comfortably fit in time limit.
Will be uploaded soon.
Can be found here.