my code for the above problem is this :
it is giving memory limit exceeded in the 22nd test case.
i want to ask that how do we handle the cases of large numbers in DP because the elements are of the order 10^9, so their sum would also be of that order. so if we want to solve the problem : subset sum such that it is divisible by m,
we will need to make a dp array of index and sum but sum goes till 10^9 which can not be made into an array. so how do we handle this?
Hi @alankrit.agr99
no need to go for dp in dis case because of the contraints.
for case n<=m, refer to dis code
can you please explain your code to me a little bit
@alankrit.agr99
in d code i m just iterating through all the element of the list and making pair and checking if mod n=0 .
like if arr=[1,2,3,4,5,],a={0}
set ts={},
first i take 1,
form pair with every element of set a, and add it to ts. so ts become ts={1} and add ts to a. so a={0,1}.
then take i=2,form pair with every element of set a, and add it to ts. so ts become ts={2,3} and add ts to a. so a={0,1,2,3}.
and so on. since size of ts can max be m, complexity of code is n*m.
Hope dis helps.
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.