### PROBLEM LINK:

### DIFFICULTY:

Cake walk

### PREREQUISITES:

None

### PROBLEM:

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 **i ^{th}** house explodes, it destroys adjacent houses. Your task is to find out the number of houses which aren’t destroyed.

### QUICK EXPLANATION:

For every house check if it is destroyed or not.

### DETAILED EXPLANATION:

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 **i ^{th}** house will be destroyed or not? It will be destroyed iff at least one of

**i-1**,

**i**and

**i+1**

^{th}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.

### SETTER’S SOLUTION:

Will be uploaded soon.

### TESTER’S SOLUTION:

Can be found here.