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.
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[1024];
private int curChar;
private int numChars;
public FasterScanner() {
this(System.in);
}
public FasterScanner(InputStream is) {
mIs = is;
}
public int read() {
if (numChars == -1)
throw new InputMismatchException();
if (curChar >= numChars) {
curChar = 0;
try {
numChars = mIs.read(buf);
} catch (IOException e) {
throw new InputMismatchException();
}
if (numChars <= 0)
return -1;
}
return buf[curChar++];
}
public String nextLine() {
int c = read();
while (isSpaceChar(c))
c = read();
StringBuilder res = new StringBuilder();
do {
res.appendCodePoint(c);
c = read();
} while (!isEndOfLine(c));
return res.toString();
}
public String nextString() {
int c = read();
while (isSpaceChar(c))
c = read();
StringBuilder res = new StringBuilder();
do {
res.appendCodePoint(c);
c = read();
} while (!isSpaceChar(c));
return res.toString();
}
public long nextLong() {
int c = read();
while (isSpaceChar(c))
c = read();
int sgn = 1;
if (c == '-') {
sgn = -1;
c = read();
}
long res = 0;
do {
if (c < '0' || c > '9')
throw new InputMismatchException();
res *= 10;
res += c - '0';
c = read();
} while (!isSpaceChar(c));
return res * sgn;
}
public int nextInt() {
int c = read();
while (isSpaceChar(c))
c = read();
int sgn = 1;
if (c == '-') {
sgn = -1;
c = read();
}
int res = 0;
do {
if (c < '0' || c > '9')
throw new InputMismatchException();
res *= 10;
res += c - '0';
c = read();
} 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;
}