Remove subarray sum to make it divisible by k

[shahayush2507]

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

[shravan660]

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

[shahayush2507]

A 4* barely qualifies as a div1

[shravan660]

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?

[shahayush2507]

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

[shravan660]

Starting index -1? Why

[shahayush2507]

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

[tamo11]

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

[shahayush2507]

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

[shravan660]

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

[shahayush2507]

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

[shravan660]

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);


     }

    }

[shahayush2507]

could you make the following changes …
make the pref array of size n+1…
and pref[0] = 0;
and the for loop … for(int i=1;i<=n;i++) pref[i] = (pref[i-1]+arr[i-1])%k

and the nxt for loop … the one after the hash map … for(int i=0;i<=n;i++) …

also take sum as long long or any big int in your case

[shahayush2507]

apparently it wasnt handling the first element

[shravan660]

broooooooooooo IT PASSSEDDDEDDDDDDDD

[shahayush2507]

all testcases ?? cool !! and you understand the soln?

[shravan660]

yes all tc broooo as i said. Div 1 are the greatest
one small doubt bro.
for(int i=0;i<=n;i++)
{
long 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);
}
Can you explain this part?
1.we take the prefix sum and why (pref[i]-m%k+k)%k?
2. If it exists, why minwith i+1-mp[reqd]?
3. why mp[pref[i]]=i+1?
only these 3 doubts bro. thank you so much for your time

[shravan660]

lets take this test case
4 6
3 1 4 2
sum= 10
pref=[0,3,4,2,2]

[shahayush2507]

[shravan660]

Woooooaahhhhhhhhhhh… you are a legend . Thanksss a lottttt