Even after watchin videos a number of time I am unable to get intution how it is solved please explain it further
Unable to understand the explanation
Hello @Divya_321,
Is there a part of logic that you didn’t understand or you want me to explain the entire logic?
If there is some specific logic, then ask all of them.
As it would be easier for me to put focus on that.
Waiting for your reply.
Actually I am not getting the intuition how pigeon hole principle is implemented in the problem, I am understanding what he is doing but unable to relate it
Hello @Divya_321,
Pigeon hole principle states that if there are more pigeons than pigeonholes, then there must be at least one pigeonhole with at least two pigeons in it.
In simple words we can say as, if n + 1 objects are put into n boxes, then at least one box contains two or more objects.
How is it related to the solution of this question?
In the example explained in the question:
-
When you computed the cumulative sum for n elements in array, it was generating n+1 sums
Reason:
You are taking the case when you are not adding any element i.e. 0 (the first element) -
After performing sum%n, the values that you can obtain after modulus will range from 0 t0 n-1 i.e. n values.
As you have to convert n partial sums to n values.
Thus, any two of those values will have same value after modulus.
Hence, satisfying this principle.
Example:
array[5]={1,1,1,1,1}
n=5;
cum_sum[n+1=6]={0,1,2,3,4,5}
cum_sum[]%n={0,1,2,3,4,0}
So, there are two same value 0 for 0 and 5.
Here these partial sums in cum_sum[] array are pigeons and the range of values(0 to n-1) are n boxes.
Hope, this would help.
Give a like if you are satisfied.
1 Like
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.