Divisilble subarray using pigeonhole principle

#1

1366×768 141 KB

why pre[0]=1 is made 1 here can anyone explain

#2

hey @sheikhhaji18 as in the array we are finding the sum and incrementing at the index of that sum also .
that why in the begining we have incremented for sum=0 that’s why he has incremented in the array when sum =0.
pre[0] means when sum is 0 increment at that index so we have pre declared it as 1.

#3

but in the starting itself pre[0]=1 why? and starting i with 0 in the loop

#4

Hey initially sum is 0 so thats why pre[sum] i.e pre[0] is 0
U can refer to this as well for deeper understanding: Why we are setting freq[0]=1;

We are starting from 0 in loop but u can also start from 1 basically u have to take n inputs

#5

another doubt why is he doing c(f,2)?

#6

(a-b)%n=0;
a%n=b%n;
each element in mod array is considered as pigeon
and the pre array is considered as pigeonhole (0–>n)
and he is selecting c(f,2)
because he is choosing the places at which a%n=b%n; right

#7

Yeah correct :slight_smile: …

#8

why he is using sum variable itself to calculate the mod and cumulative sum ,ehy is not that giving a wrong answer

#9

I think u didnt know this
(a+b)%n=(a%n+b%n)%n
So Thats why its working and also preventing an overflow

#10

ohh okay it’s property of modulo

#11

https://practice.geeksforgeeks.org/problems/sub-array-sum-divisible-by-k2617/1#
this is not passing all test cases

#12

Hey @sheikhhaji18

long long int sum=0;  //long long here
	   for(int i=0;i<n;i++){
	       sum+=arr[i];
	       sum=sum%K;
	       sum=(sum+K)%K;
	       pre[sum]++;
	   }
	   long long int ans=0;
	   for(int i=0;i<K;i++){   //<K here
	       long long int m=pre[i];
	       ans+=((m)*(m-1))/2;
	   }
#13

thx bro :upside_down_face: silly mistake becuae there are K pigeonholes

1 Like
#14

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.