Remove subarray sum to make it divisible by k

general
42

yes and yes

43

Yes yessss yessssss… I understood. :heart_eyes:

1 Like
44

bruteforce solution…

n , k = map(int, input().split())
a = list(map(int,input().split()))
total_sum = sum(a)

m = total_sum%k
if total_sum%k == 0:
print(0)
elif m in a:
print(1)
else:
ans = 999999999
while m < total_sum:
temp_sum = 0
left_ptr = 0
temp_ans = 999999999
flag = False
for i in range(n):
temp_sum += a[i]

        while left_ptr < i and temp_sum > m:
            temp_sum -= a[left_ptr]
            left_ptr += 1
        
        if temp_sum == m:
            temp_ans = min(temp_ans , i - left_ptr + 1)
            flag = True
    if flag == True:
        ans = min(ans, temp_ans)
    m += k
print(ans)

‘’’
7 4
2 1 2 6 4 6 5
1

5 4
1 2 2 6 4
5
5 4
2 1 2 6 4
1
‘’’
‘’’
Some Test Cases are wrongly given, for example take the last two test cases in the commented section. the actual answer is 1, but when i change the order of the input it’s showing wrong answer, even if the size 2 sub array elements gets swap the o/p must be same, but it’s showing wrong.

45

I wonder, even after taking action against cheaters some morons like you didn’t catch by the system…

46

if there is a case where it doesn’t solve just by removing sum%k from the current sum, it could be some other multiple which can be removed to claim the divisibility right ?
take the case
6 elements, target is to make sum divisible by 3
1 4 1 3 5 3
here the sum is 17 and 17%3 is 2 there is no sub array which sums up to 2,but here we can remove 5 which makes the sum 12 and divisible by 3 right ?

47

i am not taking the current sum … but the current sum mod k … here 5 is not 2 but 5%3 is.

48

woahhh … why?