# LEBOMBS - Editorial

Cake walk

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 ith 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 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[i] == '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[i] == '1'
will_be_destroyed[i] = 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[i])
saved_count += 1

print saved_count
``````

Both of these are O(N) solutions and very comfortably fit in time limit.

### TESTER’S SOLUTION:

Can be found here.

2 Likes

``````enter code here
``````

import java.io.;
import java.util.
;

class acm {

``````public static void main(String[] args)
{

FasterScanner sc=new FasterScanner(System.in);
int t=sc.nextInt();
while(t>0){
int n=sc.nextInt();
String s=sc.nextString();
int count=0;
for(int i=0;i<n;i++){

if(s.charAt(i)=='0'){
if(i==0){
if(s.charAt(i+1)!='1') count++;
}
else if(i==n-1){
if(s.charAt(i-1)!='1') count++;
}else{
if(s.charAt(i-1)!='1' && s.charAt(i+1)!='1') count++;
}
}
}

System.out.println(count);
t--;
}
``````

}

}

class FasterScanner {
private InputStream mIs;
private byte[] buf = new byte;
private int curChar;
private int numChars;

``````public FasterScanner() {
this(System.in);
}

public FasterScanner(InputStream is) {
mIs = is;
}

if (numChars == -1)
throw new InputMismatchException();
if (curChar >= numChars) {
curChar = 0;
try {
} catch (IOException e) {
throw new InputMismatchException();
}
if (numChars <= 0)
return -1;
}
return buf[curChar++];
}

public String nextLine() {
while (isSpaceChar(c))
StringBuilder res = new StringBuilder();
do {
res.appendCodePoint(c);
} while (!isEndOfLine(c));
return res.toString();
}

public String nextString() {
while (isSpaceChar(c))
StringBuilder res = new StringBuilder();
do {
res.appendCodePoint(c);
} while (!isSpaceChar(c));
return res.toString();
}

public long nextLong() {
while (isSpaceChar(c))
int sgn = 1;
if (c == '-') {
sgn = -1;
}
long res = 0;
do {
if (c < '0' || c > '9')
throw new InputMismatchException();
res *= 10;
res += c - '0';
} while (!isSpaceChar(c));
return res * sgn;
}

public int nextInt() {
while (isSpaceChar(c))
int sgn = 1;
if (c == '-') {
sgn = -1;
}
int res = 0;
do {
if (c < '0' || c > '9')
throw new InputMismatchException();
res *= 10;
res += c - '0';
} while (!isSpaceChar(c));
return res * sgn;
}

public boolean isSpaceChar(int c) {
return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
}

public boolean isEndOfLine(int c) {
return c == '\n' || c == '\r' || c == -1;
}
``````

}

``enter code here``

I got it…i missed the case when n=1…

#include
using namespace std;
main()
{
int t = 0 ;
cin>>t;
while(t–)
{
string inp;
int b = 0 ;
int u = 0 ;
int s = 0 ;
cin>>s;
cin>>inp;
for(int i = 0 ; i < s;i++)
{
if(inp.at(i) == ‘1’ )
{
b -= 2 ;
if(i == 0 || i == s-1)
{
b += 1 ;
}
}
else if (inp.at(i) == ‘0’)
{
u++;
}
}
cout<<b+u<<endl;
}
return 0 ;
}

why is this solution wrong?

Your code fails for this configuration

``````
1
5
10101

``````

@mohmum your code fails for 1 1 1 answer should be zero but your code prints 1

Somebody, please tell me where does my program fail?
https://www.codechef.com/viewsolution/16606169

whats wrong in my C code for the problem LEBOMBS

LEBOMBS

https://www.codechef.com/viewsolution/17048802

can anyone tell me on which values my code fails …
Thanks

https://www.codechef.com/viewsolution/17555048

Can anyone help me with this code, please?

whats wrong in my solution??
\

#include
using namespace std;
int main(){
int i,n,t,count;
cin>>t;
while(t–){
count=0;
cin>>n;
char c[n];
for(i=0;i<n;i++)
cin>>c[i];
if(c==‘0’&&c==‘0’){
count++;
}
if(c[n-1]==‘0’&&c[n-2]==‘0’){
count++;
}
for(i=1;i<(n-1);i++){
if(c[i]==‘0’){
if(c[i-1]==‘0’&&c[i+1]==‘0’)
count++;
}
}
cout<<count<<endl;
}
return 0;
}