Ok so i came across this problem in hackerearth. I have no idea how to solve this. Can someone please help me in finding the approach? It would be really helpful.

PS: this is not from any ongoing contest.

please help me. i am poor

Please someone?

itâ€™ll be helpful if you would be able to give the link to the problem.

Edit1: I was unable to find the problem using just its name.

Thanks for the reply

Click the Google coding interview

Hackerearth shuffles the questions each and every time. If you donâ€™t get the â€śRemoving the smallest subarrayâ€ť question, go back and then click the Google coding interview. Repeat it till you find the question

I think the solution to the problem would be something like this:

Take the sum of the current array, if the sum is divisible by k then the answer would be 0;

else

now you basically want to subtract the value `sum%k`

from the current sum to make it divisible by k.

For this you could have an array b ,where each element is

b_{i} = (b_{i-1} + a_{i}) % m, for all `1 <= i < n`

(0-based indexing) and b_{0} = a_{0}, and m = `sum%k`

.

You want a subarray which is a multiple of m, which basically now means , in array b,

(b_{i} - b_{j})%m = 0, meaning b_{i}%m = b_{j}%m.

So now find in the array b same elements whose indices are the least apart, and you will have you answer.

My solution.

I am unsure if my solution is correct.

Isnâ€™t this from a live contest?

nope. its just a mock interview round.

let me know if the solution works.

Yes bro. I m just typing your solution in HE. since i cannot copy paste

Bro

5 10

10 9 6 9 4

For this input, we can remove 2 sub arrays of size 1 (9 and 9) to make the sum divisible by 10.

your output is 3. you cannot remove any 3 sub array to make the sum divisible by 10.

how 3?

I am sorry if I have a wrong assumption. please clarify me. Thanks a lot for your time

im sorry , i was wrong, iâ€™ll try to rectify and get back to you.

Also you need to remove only one subarray, otherwise the solution would always have been 1. so the answer to your testcase is 4 and not 1 , remove the subarray [9,6,9,4].

Bro. You are a legend bro

â€¦ im nowhere near â€¦ i think youâ€™re being sarcastic but i have no way to tell.

Anyways , i think when i wrote â€ś`You want a subarray which is a multiple of m, which basically now means , in array b, (bi - bj)%m = 0, meaning bi%m = bj%m.`

â€ť, I have no idea what i was thinkingâ€¦ its not actually the multiple of m but its something like

b_{i} - b_{j} = k.*x* + m, where x is a variable â€¦ anything from 0 to inf.

So now taking modulo on both sides by k i would get â€¦ (b_{i} - b_{j} )%k = (k.*x* + m)%k â€¦

b_{i}%k - b_{j}%k = m%k.

soln

If this doesnâ€™t work sorry to waste your time â€¦ and let me know once you get the correct solution.

Bro. Seriously you are great and I am not sarcastic. It is actually written in history. Alexander was called the great, div 1 are called the great

A 4* barely qualifies as a div1

Bro. What is Bj here? I suppose that Bi is the starting of the sub array and Bj is the ending of the same sub array. Is it right?

correct â€¦ bj is the ending and bi is starting index - 1 actually.

does this pass

Starting index -1? Why

because in a prefix sum array when you want to take the sum of the subarray then you subtract the ending index sum with the sum at starting index-1