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.
