### infj1's blog

By infj1, history, 3 months ago,

Given an array of length n containing only zeros and ones, you can perform operations by removing either the first or the last element of the array. Calculate the minimum number of operations required to achieve a total sum of s in the array. If it is not possible to obtain the sum s after any number of operations, the output should be -1.

The code below is my approach. But when I submit its giving wrong answer. Could you guys what's the problem with the code? Or the approach?

for _ in range(int(input())):

n,s=[int(i) for i in input().split()]

a=[int(i) for i in input().split()]

c=0

for i in range(n):

if a[i]==1:
c+=1

if c<s:
print(-1)
else:
l=0
r=n-1
req=c-s
got=0
ans=0
if got==req:
print(0)
continue
while l<r and got<req:
old_l=l
while l<r and a[l]==0:
l+=1
old_r=r
while r>l and a[r]==0:
r-=1
l_dis=l-old_l
r_dis=old_r-r
if l_dis<r_dis:
r=old_r
ans+=l_dis+1
l+=1
else:
l=old_l
ans+=r_dis+1
r-=1
got+=1
print(ans)
• -4

 » 3 months ago, # |   0 Auto comment: topic has been updated by infj1 (previous revision, new revision, compare).
 » 3 months ago, # |   0 There can only be 3 cases if you can get sum: 1. You obtain sum via some prefix in the array lets say [1, L] 2. You obtain sum via some suffix in the array lets say [R, N] 3. You obtain sum via some prefix + suffix lets say [1, Li] + [Ri, N] Enumerate all cases using prefix and suffix sums (suffix sum not required) and ans is just sum of above ranges.
•  » » 3 months ago, # ^ |   0 I mean min of sum of all possible ranges*
 » 3 months ago, # |   0 Essentialy, your task is to find a pair $(l, r) : \sum\limits_{i=l}^{r} a[i] = s$, which maximizes $r - l$. The problem of finding the largest subsegment with $sum <= k$ can be solved with two pointers technique (if you're not familiar with it, the EDU section might be helpful).