# Leetcode:K Empty Slots

There is a garden with N slots. In each slot, there is a flower. The N flowers will bloom one by one in N days. In each day, there will be exactly one flower blooming and it will be in the status of blooming since then.

Given an array flowers consists of number from 1 to N. Each number in the array represents the place where the flower will open in that day.

For example, flowers[i] = x means that the unique flower that blooms at day i will be at position x, where i and x will be in the range from 1 to N.

Also given an integer k, you need to output in which day there exists two flowers in the status of blooming, and also the number of flowers between them is k and these flowers are not blooming.

If there isn't such day, output -1.

Example 1:

``````Input:
flowers: [1,3,2]
k: 1
Output: 2
Explanation: In the second day, the first and the third flower have become blooming.
``````

Example 2:

``````Input:
flowers: [1,2,3]
k: 1
Output: -1
``````

Note:

``````The given array will be in the range [1, 20000].
``````

``````#include <stdio.h>

int lowbit(int x);
int kEmptySlots(int* flowers, int flowersSize, int k);
void insert(int i,int x,int *c);
int getsum(int i,int *c);

int main(void)
{
int flowers={1,2,3,4};
printf("%d",kEmptySlots(flowers,4,1));
return 0;
}

int kEmptySlots(int* flowers, int flowersSize, int k)
{
int trarray={0};
int base={0};
{
insert(flowers[i],1,trarray);
base[i]=getsum(flowers[i],trarray);
}
{
if(base[j+k+1]-base[j]==k)
{
//printf("%d",j+k+1);
return j+k+1;
}
}
return -1;
}

int lowbit(int x) //定义一个Lowbit函数，返回参数转为二进制后,最后一个1的位置所代表的数值.
{
return x&(-x);
}

void insert(int i,int x,int *c)
{
while(i<=10)  //维护c数组
{
c[i]+=x;
i+=lowbit(i);
}
}
int getsum(int i,int *c) //比i小的数
{
int sum=0;
while(i>0)
{
sum+=c[i];
i-=lowbit(i);
}
return sum;
}``````
Posted in ACM