After knowing positions of bat:

**For 50 Points:**

lets say **k = "110"**

ans positions of bats are: **A = [2,3]**; Then

Just make an array call it **SUM** of size highest element of A + size of k (I am caring about carry here and finding sum for ith position SUM array), with all elements 0; Then

**SUM = [0,0,0,0,0,0]**

now just update **SUM** array in range(shift, shift + size of k), because while shifting we are adding 0 at back so shifting will affect only this range of SUM [shift, shift+size of k], so after choosing 2 SUM will become:

**SUM = [0,0,0,1,1,0]** (I am taking k in opposite direction to make it clear for shifting and changing it binary in later part)

After second part it will become:

**SUM = [0,0,0,1,2,1]**

Then we can convert this array to binary string easily by just traversing from left to right and using carry. so answer will become:

**ANS = “0001001”** then reverse it again, because we reverse it initially for our convenience.

**ANS = "1001000"**

So basically this solution will give complexity of **O(numberOfBatsPositions*size(k))** so, third case will pass because max numberOfBatsPositions can be 1000000(b upper limit) and size(k) <= 60

You can follow my solution here for same. Follow code after this line for above steps:

```
ll kLen = k.length();
```

**For 100 Points:**

Now convert k into a signal. let’s make an array which stores pos of ones in it. Because once SUM array is calculated then we are done(because it was main time consuming part). For Example if:

**k = “110” => reverseK = “011”** (because for convenience we were taking SUM array reverse for clarity of shifting and addition later)

**then onePos = [2,3] (1 Indexed)** this is our first signal;

and second signal is shifting array. [2,3].

Now for calculating SUM we have to start SUM with all 0 and update it like this:

```
SUM = [0,0,0,0,0,0]
for i in onePos:
for j in shifts:
SUM[i+j] += 1
```

but again this would be of same order as above. Now above operation can be done in **O(NLog(N))** instead of **O(N^2)** by **finding convolution using FFT**. In simple terms you can find convolution using FFT in python like this:

```
import scipy.signal
def hist(X):
h = [0]*(max(X)+1)
for x in X:
h[x] += 1
return h
onePos = [2,4]
shifts = [1,3]
print scipy.signal.fftconvolve(hist(onePos),hist(shifts))
```

here histogram is doing nothing but calculating frequencies of each element in array for FFT convolution.

**I know this solution looks too messy, but hope it’s clear enough to understand**.