package array;

/**

* Created by gouthamvidyapradhan on 10/06/2017.

* Accepted

*

Suppose you have a long flowerbed in which some of the plots are planted and some are not. However, flowers cannot be planted in adjacent plots - they would compete for water and both would die.

Given a flowerbed (represented as an array containing 0 and 1, where 0 means empty and 1 means not empty), and a number n, return if n new flowers can be planted in it without violating the no-adjacent-flowers rule.

Example 1:

Input: flowerbed = [1,0,0,0,1], n = 1

Output: True

Example 2:

Input: flowerbed = [1,0,0,0,1], n = 2

Output: False

Note:

The input array won't violate no-adjacent-flowers rule.

The input array size is in the range of [1, 20000].

n is a non-negative integer which won't exceed the input array size.

*/

public class CanPlaceFlowers

{

/**

* Main method

* @param args

* @throws Exception

*/

public static void main(String[] args) throws Exception

{

int[] n = {1,0,0,0,1};

System.out.println(new CanPlaceFlowers().canPlaceFlowers(n, 1));

}

public boolean canPlaceFlowers(int[] flowerbed, int n) {

int[] T = new int[flowerbed.length + 4];

for(int i = 0, j = 2; i < flowerbed.length; i ++)

T[j++] = flowerbed[i];

T[0] = 1;

T[T.length - 1] = 1;

int total = 0, count = 0;

for(int i = 1; i < T.length; i ++) {

if(T[i] == 0)

count++;

else {

if((count % 2) == 0)

total += ((count / 2) - 1);

else

total += (count / 2);

count = 0; //reset

}

}

return (total >= n);

}

}