Linkedin Interview Question
Applications DevelopersCountry: United States
Interview Type: Phone Interview
public static boolean canPlant(boolean[] arr, int count){
if(arr == null){
throw new NullPointerException();
}
int locations = 0;
boolean lastPos = false, thisPos = false, nextPos = arr[0];
int index = 1;
while(index < arr.length){
lastPos == thisPos;
thisPos = nextPos;
nextPos = arr[index];
if(!(lastPos || thisPos || nextPos)){
locations ++
if(locations >= count){
return true;
}
}
index++;
}
if(index == arr.length && !(thisPos || nextPos)){
locations++;
}
return locations <= count;
}
public class Main {
public static void main(String[] args) {
int no_of_beds = 3 ;
int no_of_possible_beds = 0 ;
byte[] TestBed = new byte[] {0,1,0,0,0,0,0,1,0,0};
for (int i = 0; i < TestBed.length; i++) {
// approach1:for each 1, skip one i and see if we have zero in i+2,
// if yes, assign the Flower in i+2
/*if( TestBed[i] == 1 && (i+2 <TestBed.length) && TestBed[i+2] == 0) {
//TestBed[i+2] = 1; // this step is must for this approch
no_of_possible_beds++;
}*/
// approach2:for two consecutive zeros, we can increase the no_of_possible_beds and
// also skip the recent zero.Note below code is with no replacement in TestBed.
// We just estimate the possibility of fitting
if(TestBed[i]== 0 && i-1 >= 0 && TestBed[i-1] == 0) {
no_of_possible_beds ++ ;
i++;
}
}
System.out.print(no_of_possible_beds >= no_of_beds? true:false);
}
}
public class Main {
public static void main(String[] args) {
int no_of_beds = 3 ;
int no_of_possible_beds = 0 ;
byte[] TestBed = new byte[] {0,1,0,0,0,0,0,1,0,0};
for (int i = 0; i < TestBed.length; i++) {
// approach1:for each 1, skip one i and see if we have zero in i+2,
// if yes, assign the Flower in i+2
/*if( TestBed[i] == 1 && (i+2 <TestBed.length) && TestBed[i+2] == 0) {
//TestBed[i+2] = 1; // this step is must for this approch
no_of_possible_beds++;
}*/
// approach2:for two consecutive zeros, we can increase the
// no_of_possible_beds
// also skip the recent zero.Note below code is with no replacement in TestBed.
// We just estimate the possibility of fitting
if(TestBed[i]== 0 && i-1 >= 0 && TestBed[i-1] == 0) {
no_of_possible_beds ++ ;
i++;
}
}
System.out.print(no_of_possible_beds >= no_of_beds? true:false);
}
}
private static boolean canPlant(int[] plantArr, int i) {
boolean canPlant=false;
if(i==0)
{
if(plantArr[i]==0 && plantArr[++i]==0)
{
canPlant=true;
}
}
else if(i==plantArr.length-1)
{
if(plantArr[i]==0 && plantArr[--i]==0)
{
canPlant=true;
}
}
else if(i>0 && i< plantArr.length-1 )
{
if(plantArr[i]==0 && plantArr[i+1]==0 && plantArr[i-1]==0)
{
canPlant=true;
}
}
return canPlant;
}
Always check if the current plot is free if so then check if the next plot is free, if so then then we can plant a flower there, if the current plot is not free then go to next to next plot.
If current plot is free but next plot is not free then go to 3rd plot from current one.
By moving like this we can make sure we only need to check the current and next and need not worry about the previous one.
public static boolean canPlant(int[] input,int n){
int size = input.length;
int planted = 0;
int i=0;
while(i < size) {
if(input[i] == 0 ){
if(input[i+1] == 0){
planted++;
i+=2;
}else{
i+=3;
}
}else{
i+=2;
}
if(planted == n ){
return true;
}
}
return false;
}
This is working code, but needs to add check for invalid inputs
like when n <= 0 or a is null
Solution using state machine:
public enum PlotState
{
OnFlower,
OnEmpty,
AboutToPlant,
}
public static bool CanPlaceFlowers(List<bool> flowerbed, int numberToPlant)
{
int numberOfPlots = flowerbed.Count();
if (numberOfPlots < (numberToPlant * 2 - 1))
{
return false;
}
if (numberToPlant == 0)
{
return true;
}
int planted = 0;
PlotState state = PlotState.OnEmpty;
for (int i = 0; i < numberOfPlots; i++)
{
bool current = flowerbed[i];
switch (state)
{
case PlotState.AboutToPlant:
if (current)
{
state = PlotState.OnFlower;
}
else
{
state = PlotState.OnEmpty;
planted++;
if (planted == numberToPlant)
{
return true;
}
}
break;
case PlotState.OnEmpty:
if (current)
{
state = PlotState.OnFlower;
}
else
{
state = PlotState.AboutToPlant;
}
break;
case PlotState.OnFlower:
if (current)
{
// do nothing, state is the same
}
else
{
state = PlotState.OnEmpty;
}
break;
}
}
if (state == PlotState.AboutToPlant)
{
state = PlotState.OnFlower;
planted++;
if (planted == numberToPlant)
{
return true;
}
}
return false;
}
In C, it is a little bit of work to create doubly linked list.
#include<stdio.h>
#include<stdlib.h>
typedef struct ListNode {
int item;
struct ListNode *next;
struct ListNode *prev;
} node;
typedef struct List {
int size;
struct ListNode *head;
struct ListNode *tail;
} list;
node * createNode(int item) {
node * newnode = (node *) malloc(sizeof(node));
newnode->item = item;
newnode->next = NULL;
newnode->prev = NULL;
return newnode;
}
void insertNodeEnd(list * listFlower, int item) {
if (listFlower->head == NULL) {
listFlower->head = createNode(item);
listFlower->tail = listFlower->head;
listFlower->size++;
}
else {
node * conductor = listFlower->head;
while (conductor->next != NULL) {
conductor = conductor->next;
}
conductor->next = createNode(item);
conductor->next->prev = conductor;
listFlower->tail = conductor->next;
listFlower->size++;
}
}
void displayNode(list *listFlower) {
node * conductor = listFlower->head;
while (conductor != NULL) {
printf("%d ", conductor->item);
conductor = conductor->next;
}
printf("\n");
}
void displayNodeBackward(list *listFlower) {
node * conductor = listFlower->tail;
while (conductor != NULL) {
printf("%d ", conductor->item);
conductor = conductor->prev;
}
printf("\n");
}
int canPlaceFlowers(list * listFlower, int n) {
if (n > listFlower->size) {
return 0;
}
if (n == 0) {
return 1;
}
else if ( n==1 ) {
if (listFlower->size == 1) {
if (listFlower->head->item == 0) {
return 1;
}
else {
return 0;
}
}
}
int count = 0;
if (listFlower->head == NULL) {
return 0;
}
else {
node * conductor = listFlower->head;
while (conductor->next != NULL) {
if (conductor->prev != NULL) {
if (conductor->item == 0 && conductor->prev->item == 0 && conductor->next->item == 0) {
count++;
conductor->item = 1;
}
}
else {
if (conductor->item == 0 && conductor->next->item == 0) {
count++;
conductor->item = 1;
}
}
conductor = conductor->next;
}
if (conductor->prev->item == 0 && conductor->item == 0) {
count++;
conductor->item = 1;
}
if (count >= n) {
return 1;
}
else {
return 0;
}
}
}
int main() {
node *head = NULL;
node *tail = NULL;
list *listFlower = (list *) malloc(sizeof(list));
listFlower->head = head;
listFlower->tail = tail;
listFlower->size = 0;
int f, n = 10;
//printf("Please input the flowers in the flowerbed:(1 or 0)");
int array[10] = { 0, 0, 1, 0, 0, 0, 1, 0, 0, 0 };
//int array[2] = { 0, 0 };
for (int i = 0; i < n; i++) {
//scanf("%d", &f);
insertNodeEnd(listFlower, array[i]);
}
displayNode(listFlower);
displayNodeBackward(listFlower);
int numFlower;
printf("Please input the number of flowers that you want to plant:");
printf("How many flowers? ");
scanf("%d", &numFlower);
int can = canPlaceFlowers(listFlower, numFlower);
if (can) {
printf("\ntrue\n");
}
else {
printf("\nfalse\n");
}
}
This is a java Solution.
I think it is pretty straightforward. Enjoy
public boolean canPlaceFlowers(List<Boolean> flowerbed, int numberToPlace) {
if (flowerbed == null || flowerbed.size() == 0 || flowerbed.size() < numberToPlace)
return false;
int size = flowerbed.size();
if (numberToPlace == 0) {
return true;
}
flowerbed.add(0, true);
flowerbed.add(size - 1, true);
int pre = 0;
int can = 0;
for(int i = 1; i < flowerbed.size(); i++){
if(flowerbed.get(i) == true){
can += i - pre - 2;
pre = i;
}
}
return can >= numberToPlace;
}
public boolean canPlaceFlowers(List<Boolean> flowerbed, int numberToPlace) {
if (flowerbed == null || flowerbed.size() == 0 || flowerbed.size() < numberToPlace)
return false;
int size = flowerbed.size();
if (numberToPlace == 0) {
return true;
}
flowerbed.add(0, true);
flowerbed.add(size - 1, true);
int pre = 0;
int can = 0;
for(int i = 1; i < flowerbed.size(); i++){
if(flowerbed.get(i) == true){
can += i - pre - 2;
pre = i;
}
}
return can >= numberToPlace;
}
if (flowerbed == null || flowerbed.size() == 0 || flowerbed.size() < numberToPlace)
return false;
int size = flowerbed.size();
if (numberToPlace == 0) {
return true;
}
flowerbed.add(0, true);
flowerbed.add(size - 1, true);
int pre = 0;
int can = 0;
for(int i = 1; i < flowerbed.size(); i++){
if(flowerbed.get(i) == true){
can += i - pre - 2;
pre = i;
}
}
return can >= numberToPlace;
}
int max(int a[], int currentindex)
{
if(currentindex == a.length) return 0;
if(a[i] == 0)
{
if((i<1 || a[i-1] == 0) && (i>a.length-2 || a[i+1]==0))
{
a[i] = 1;
x = max(a,i+1) + 1
a[i] = 0;
if(incache(i+1) y= cache;
else { y = max(a,i+1); addtocache(i+1,y); }
return x>y?x:y;
}
}
return max(A,i+1);
}
bool canplace(int a[], int numtoplace)
{
int maxplacable = max(a,0);
if(numtoplace< maxplacable) return true;
return false;
}
We don't even need to write much code for the problem. By counting the number of "1" and "0" in the array plus checking the first and last element give us the answer.
Every "1" in the middle of the array will take two "0"
Every "1" at the begin or end of the array will take one "0"
Every "0" at the begin or end of the array will counter balance the one (you can imagine there is another 0 on the side of the array).
Therefore we can do:
x0 = number of 0
x1 = number of 1
x00 = number of 0 at the start or end of the array
x11 = number of 1 at the start or end of the array
res0 (# of 0 free in the array) = x0 - x1 * 2 - x11 + x00 x 2
res1 (# of plant that we can add) = (res0 - res0/2)
For 100000100. We get 6*"0"-1x"1"-1x"1"+1x"0"
=> 6*1-1*2-1*1+1*2 = 6-2-1+2 = 5
Only 5 zero a free somewhere in the array which allow you to only 3 plant. (5 - 5/2)
For 100100100. We got 5x"0"-2x"1"-1x"1"+1x"0"
=> 5x1-2x2-2x1+1x2 => 5-4-1+2 = 2.
Only 2 zero a free somewhere in the array which allow you to only 1 plant. (2 - 2/2)
Here is the C++ version of solution
Running time is O(N).
#include<iostream>
using namespace std;
bool plant_flowers(int* input, int len, int target)
{
int i = 0;
int count = 0;
while(i < len)
{
if (input[i] != 1)
{
if (i-1<0 ||input[i-1] != 1)
{
if (i+1>len||input[i+1] !=1)
{
input[i] = 1;
count++;
i+=2;
} else {
i += 3;
}
} else {
i+=2;
}
} else {
i+=2;
}
}
return count >= target;
}
public static void main(String[] args) {
int[] array = {1, 0, 0, 0, 0, 0, 0, 0, 1, 0 ,0, 0, 0};
//int[] array = {1, 0, 0, 1, 0, 0, 1, 0 ,0};
System.out.println("Max Flowers = " + getMaxFlowers(array));
}
public static int getMaxFlowers(int[] array) {
System.out.println("Original Array = " + Arrays.toString(array));
// Sanitize the array.
for(int i = 0; i < array.length; i++) {
// Store -1 on the neighborhoods of 1's
if(array[i] == 1) {
if(i > 0 && array[i-1] == 0) array[i-1] = -1;
if(i < array.length - 1 && array[i+1] == 0) array[i+1] = -1;
}
}
System.out.println("Modified Array = " + Arrays.toString(array));
return getMaxFlowers(array, 0, 0);
}
public static int getMaxFlowers(int[] array, int index, int curCount) {
if(index >= array.length)
return curCount;
while(index < array.length && array[index] != 0) index++;
if(index < array.length) {
int[] newArray = array.clone();
if(index > 0) newArray[index-1] = -1;
newArray[index] = 1;
if(index < array.length - 1) newArray[index+1] = -1;
System.out.println("Old Array = " + Arrays.toString(array) + " Count = " + curCount);
System.out.println("New Array = " + Arrays.toString(newArray) + " Count = " + curCount);
int res1 = getMaxFlowers(newArray, index + 2, curCount + 1);
int res2 = getMaxFlowers(array, index + 1, curCount);
return Math.max(res1, res2);
}
return curCount;
}
ROCK SOLID SOLUTION O(n)
public static int simpleGetMaxFlowers(int[] array) {
if(array == null) return 0;
int maxFlowers = 0;
for(int i = 0; i < array.length; i++) {
if(array[i] == 0) {
if((i > 0 && array[i-1] == 1) || (i < array.length - 1 && array[i+1] == 1))
continue;
array[i] = 1;
maxFlowers++;
}
}
return maxFlowers;
}
public static boolean placeOnes(int arr[], int start, int n)
{
if (n == 0)
return true;
if (start >= arr.length)
return false;
for (int index = start; index < arr.length; index++)
{
if (arr[index] == 0 &&
((index == 0 && arr[index + 1] == 0) || (index == arr.length - 1 && arr[index - 1] == 0) ||
(index >= 1 && index <= arr.length - 2 && arr[index - 1] == 0 && arr[index + 1] == 0)))
{
arr[index] = 1;
if (placeOnes(arr, index + 1, n - 1))
return true;
else
{
arr[index] = 0;
}
}
}
return false;
}
public boolean canPlaceFlowers(List<Boolean> flowerbed, int numberToPlace) {
// Implementation here
boolean flag = flowerbed[0] == true ? false : true;
if(flag)
numberToPlace--;
for(int count = 1; count < flowerbed.size() - 1; count++) {
if(numberToPlace == 0) {
break;
}
if(flag && !flowerbed.get(count-1) && !flowerbed.get(count+1)) {
numberToPlace--;
}
flag = !flag;
}
return numberToPlace == 0;
}
public boolean canPlaceFlowers(List<Boolean> flowerbed, int numberToPlace) {
if(flowerbed.size() == 1) {
return !flowerbed.get(0);
}
// Implementation here
boolean flag = flowerbed.get(0) == true ? false : true;
if(flag)
numberToPlace--;
for(int count = 1; count < flowerbed.size() - 1; count++) {
if(numberToPlace == 0) {
break;
}
if(flag && !flowerbed.get(count-1) && !flowerbed.get(count+1)) {
numberToPlace--;
}
flag = !flag;
}
return numberToPlace == 0;
}
int plant(boolean[] b) {
if (b.length == 0) return 0;
plant(b, 0);
}
int plant(boolean[] b, int index) {
if (index >= b.length) return 0;
if (b[index]) return plant(b, index + 1);
else {
boolean before = (index - 1 >= 0) ? b[index-1] : false;
boolean after = (index + 1 < b.length) ? b[index+1] : false;
// if both are false
if (!(before || after)) {
b[index] = true;
return plant(b, index + 1) + 1;
}
}
}
// C++ Code with vector as a container
// First a function that checks if a flower can be planted at a specific location.
// If a flower can be planted, it will plant a flower and return true
vector<bool> flowerbed;
const int FLOWERBED_SZ = 16;
void init() {
flowerbed.reserve(FLOWERBED_SZ);
for (int i = 0; i < flowerbed.size(); i++) {
flowerbed[i] = false;
}
// Make random placement of flower
flowerbed[0] = true;
flowerbed[4] = true;
}
bool canPlaceFlower(vector<bool> & fb, int i) {
// For first position, only check the next one
if (i == 0) {
if (fb[i+1] == false) {
fb[i] = true;
return true;
}
}
// For last position, check only the previous
if (i == fb.size() - 1) {
if (fb[i-1] == false) {
fb[i] = true;
return true;
}
}
// Check both the previous and next position
if (fb[i-1] == false && fb[i+1] == false) {
fb[i] = true;
return true;
}
// Cannot plant flower
return false;
}
int countPlacements(vector<bool> &fb) {
int count = 0;
for (int i = 0; i < fb.size(); i++) {
if (canPlaceFlower(fb, i)) {
count++;
}
}
return count;
}
int main() {
init();
cout << " Count of max that can be planted "
<< countPlacements(flowerbed) << endl;
}
#include <cstdio>
#include <string>
#include <cstring>
#include <string>
using namespace std;
/*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 booleans), return if a given number of new flowers can be planted in it without violating the no-adjacent-flowers rule
Sample inputs
Input: 1,0,0,0,0,0,1,0,0
3 => true
4 => false
Input: 1,0,0,1,0,0,1,0,0
1 => true
2 => false
input: 0
1 => true
2 => false */
int main()
{
int len_list;
//int a[100];
int i = 0;
int n, max_plots;
n = 9;
int a[] = { 1,0,0,0,0,0,1,0,0 };
a[n] = 0;
max_plots = 3;
for (i = 0; i < n; i++)
{
if ((a[i] == 0) && (a[i - 1] == 0) && (a[i + 1] == 0))
{
printf(" position %d\n", i);
a[i] = 1;
max_plots--;
}
}
if (max_plots <= 0)
printf("Success");
else printf("Failure");
scanf_s("%d", &n);
}
public static boolean canPlaceFlowers(List<Boolean> flowerbed,
int numberToPlace) {
// Implementation here
// Count for if we can place an adjacent flower
int cntCanAddFlower = 0;
// condtion to check if adjacent flower can be set
boolean prev = flowerbed.get(0) == true ? true : false;
// check the next index
// if its false
// increment the count
for (Boolean next : flowerbed) {
if (!next && !prev )
cntCanAddFlower++;
else if (next)
cntCanAddFlower--;
prev = next;
}
System.out.println(cntCanAddFlower);
// compare count to numbertoPlace -> return result
if (cntCanAddFlower == numberToPlace)
return true;
else
return false;
}
public static boolean canPlaceFlowers(List<Boolean> flowerbed,
int numberToPlace) {
// Implementation here
// Count for if we can place an adjacent flower
int cntCanAddFlower = 0;
// condtion to check if adjacent flower can be set
boolean prev = flowerbed.get(0) == true ? true : false;
// check the next index
// increment the count if current and
// previous flags are false
// if current flag is true decrement count
for (Boolean next : flowerbed) {
if (!next && !prev )
cntCanAddFlower++;
else if (next)
cntCanAddFlower--;
prev = next;
}
System.out.println(cntCanAddFlower);
// compare count to numbertoPlace -> return result
if (cntCanAddFlower >= numberToPlace)
return true;
else
return false;
}
public static boolean canPlaceFlowers(List<Boolean> flowerbed, int numberToPlace) {
int placed = 0;
for(int i=0;i<flowerbed.size();i++){
if(flowerbed.get(i) || (i>0 && flowerbed.get(i-1)) || (i<flowerbed.size()-1 && flowerbed.get(i+1))){
continue;
}
flowerbed.set(i, true);
placed++;
}
if(placed>=numberToPlace){
return true;
}
return false;
}
public class CanBePlaced {
public static boolean canPlaceFlowers(List<Boolean> flowerbed, int numberToPlace) {
int capacity = 0;
int size = flowerbed.size();
for (int i = 0; i < size; i++) {
if(flowerbed.get(i)) {
i ++;
} else {
if (i == size - 1 || !flowerbed.get(i + 1)) {
capacity ++;
i ++;
}
}
}
return numberToPlace <= capacity;
}
public static void main(String[] args) {
System.out.println(canPlaceFlowers(toBools(asList(0,0,1,0,0,1,0,0)), 2));
}
private static List<Boolean> toBools(List<Integer> integers) {
return integers.stream().map(e -> e == 1).collect(Collectors.toList());
}
}
public static bool FlowerBedPlant(int[] arr, int n)
{
for(int i=0; i<arr.Length; i++)
{
if (arr[i] == 1) continue;
if (i > 0 && i < arr.Length - 1 && arr[i - 1] == 0 && arr[i + 1] == 0)
{
arr[i] = 1;
n--;
}
else if (i == 0 && i < arr.Length - 1 && arr[i + 1] == 0)
{
arr[i] = 1;
n--;
}
else if (i == arr.Length - 1 && arr[i-1]==0)
{
arr[i] = 1;
n--;
}
}
return n == 0;
}
package keshy.threads;/*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 booleans), return if a given number of new flowers can be planted in it without violating the no-adjacent-flowers rule
Sample inputs
Input: 1,0,0,0,0,0,1,0,0
3 => true
4 => false
*/
public class CanPlant {
public final int[] flowerbed;
public int totalAvailable = 0;
public CanPlant(int[] arr) {
if(arr.length == 0) {
throw new IllegalArgumentException("Cannot initialize an empty flowerbed");
}
flowerbed = arr;
evaluateAvailablePlots();
}
public void evaluateAvailablePlots() {
if(flowerbed[0] != 1 && flowerbed[1] == 0) {
flowerbed[0] = 1;
totalAvailable++;
}
if(flowerbed[flowerbed.length - 1] != 1 && flowerbed[flowerbed.length - 2] == 0) {
flowerbed[flowerbed.length - 1] = 1;
totalAvailable++;
}
for(int i = 1; i <= flowerbed.length - 2; i++) {
// check prev and next position
if(flowerbed[i] != 1 && flowerbed[i-1] == 0 && flowerbed[i+1] == 0) {
flowerbed[i] = 1;
totalAvailable++;
}
}
}
public boolean canPlant(int number) {
return number<=totalAvailable;
}
public static void main(String... args) {
int[] arr = new int[]{1,0,0,0,0,0,1,0,0};
CanPlant s = new CanPlant(arr);
System.out.println(s.canPlant(4));
}
}
package keshy.threads;/*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 booleans), return if a given number of new flowers can be planted in it without violating the no-adjacent-flowers rule
Sample inputs
Input: 1,0,0,0,0,0,1,0,0
3 => true
4 => false
*/
public class CanPlant {
public final int[] flowerbed;
public int totalAvailable = 0;
public CanPlant(int[] arr) {
if(arr.length == 0) {
throw new IllegalArgumentException("Cannot initialize an empty flowerbed");
}
flowerbed = arr;
evaluateAvailablePlots();
}
public void evaluateAvailablePlots() {
if(flowerbed[0] != 1 && flowerbed[1] == 0) {
flowerbed[0] = 1;
totalAvailable++;
}
if(flowerbed[flowerbed.length - 1] != 1 && flowerbed[flowerbed.length - 2] == 0) {
flowerbed[flowerbed.length - 1] = 1;
totalAvailable++;
}
for(int i = 1; i <= flowerbed.length - 2; i++) {
// check prev and next position
if(flowerbed[i] != 1 && flowerbed[i-1] == 0 && flowerbed[i+1] == 0) {
flowerbed[i] = 1;
totalAvailable++;
}
}
}
public boolean canPlant(int number) {
return number<=totalAvailable;
}
public static void main(String... args) {
int[] arr = new int[]{1,0,0,0,0,0,1,0,0};
CanPlant s = new CanPlant(arr);
System.out.println(s.canPlant(4));
}
}
#include <iostream>
#include <vector>
#include <list>
using namespace std;
bool canPlace(list<bool> bed, int xFlowers) {
int m = 0, n = xFlowers;
if(xFlowers == 0) return true;
if(bed.size()==1) {
if(bed.front() == false && n ==1) {
return true;
}
return false;
}
list<bool>::iterator it1 = bed.begin(), it2 = bed.begin(), it3 = bed.begin();
++it2;
++it3; ++it3;
for( ;it3!=bed.end();) {
if(*it1 == false && *it2==false && *it3==false) {
++m;
*it2 = true;
}
++it1; ++it2; ++it3;
}
if(bed.size() > 1) {
//it3 = bed.back(); it2 = it3 - 1;
it3 = it2;
it2 = it1;
if(*it3 == false && *it2 == false) {
++m; *it3 = true;
}
it1 = bed.begin(); it2 = bed.begin(); ++it2;
if(*it1 == false && *it2 == false) {
++m; *it1 = true;
}
}
return m>=n;
}
int main() {
// your code goes here
int arr[] = {0,1,0,0,1,0,0 };
list<bool> bed;
//int array[2] = { 0, 0 };
for (int i = 0; i < sizeof(arr)/sizeof(int); i++) {
//scanf("%d", &f);
bed.push_back((bool)arr[i]);
}
cout<<canPlace(bed, 1);
return 0;
}
- aj June 02, 2015