Remove subarray sum to make it divisible by k

general
6

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
7

Isn’t this from a live contest?

1 Like
8

nope. its just a mock interview round.

1 Like
9

let me know if the solution works.

10

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

11

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

12

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].

13

Bro. You are a legend bro

14

:joy::joy::joy::joy::joy: … 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
15

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

16

A 4* barely qualifies as a div1

17

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?

18

correct … bj is the ending and bi is starting index - 1 actually.
does this pass

19

Starting index -1? Why

20

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

21

i think u forgot to take cases like-
3 6
9 8 8
just this line “if(mn==inf) mn=n;” before printing answer would rectify it though

22

yes … i think initializing mn to be n would’ve been enough

23

(bi-bj)%k=(k.x+m)%k…
how did it become bi%k-bj%k=m%k.?
what is k here

24

k is the number given to us n k a1,a2,a3 .... here.when we expand the modulo …
bi%k - bj%k = kx%k + m%k … now since kx%k would be 0 since kx is divisible by k

26

bro 10/20 cases passes bro
public static void main(String args[] ) throws Exception {
Scanner s=new Scanner(System.in);
int n=s.nextInt(),k=s.nextInt();
int arr[]=new int[n];
int sum=0;
for(int i=0;i<n;i++)
{
arr[i]=s.nextInt();
sum+=arr[i];
}
if(sum%k==0)
System.out.println(0);
else
{
int pref[]=new int[n];
pref[0]=arr[0]%k;
for(int i=1;i<n;i++)
{
pref[i]=(pref[i-1]+arr[i])%k;

     }
     int m=sum%k;
     int mn=n;
     HashMap<Integer,Integer> mp=new HashMap<Integer,Integer>();
     for(int i=0;i<n;i++)
     {
         int reqd=(pref[i]-m%k+k)%k;
         if(mp.containsKey(reqd))
         {
            mn=Math.min(mn,i+1-mp.get(reqd)); 
         }
        mp.put(pref[i],i+1); 
     }
     
     System.out.println(mn);


     }

    }