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
yes … i think initializing mn to be n would’ve been enough
(bi-bj)%k=(k.x+m)%k…
how did it become bi%k-bj%k=m%k.?
what is k here
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
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);
}
}
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
apparently it wasnt handling the first element
broooooooooooo IT PASSSEDDDEDDDDDDDD
all testcases ?? cool !! and you understand the soln?
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
lets take this test case
4 6
3 1 4 2
sum= 10
pref=[0,3,4,2,2]
Woooooaahhhhhhhhhhh… you are a legend . Thanksss a lottttt
quite sarcastic … you’re welcome
Never sarcastic
keep posting such interesting problems
Bro in the 5th line in 2nd pic. “Now take modulo with k” why do we do that?
just to make the equation easier!
long reqd=(pref[i]-m%k+k)%k;
In this, will it work (pref[i]-m+k)%k;
Since m is already a mod of k(ie, from (0,k-1))?
So according to the photo. i is the ending and j is the starting?