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.
3 Likes
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
bi = (bi-1 + ai) % m, for all 1 <= i < n (0-based indexing) and b0 = a0, and m = sum%k.
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.
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.
1 Like
Isn’t this from a live contest?
1 Like
nope. its just a mock interview round.
1 Like
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
bi - bj = 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 … (bi - bj )%k = (k.x + m)%k …
bi%k - bj%k = m%k.
soln
If this doesn’t work sorry to waste your time … and let me know once you get the correct solution.
2 Likes
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