CODEWITHSUNDEEP
algorithmtime-complexitydynamic-programmingsubset-sum
Samay Bhardwaj
Samay Bhardwaj

Reputation: 21

Subset sum of P elements (with repetition allowed) divisible by M

Given an array A of N elements. We need to find the number of subsets (with repetition of numbers allowed) such that the number of elements in the subset is P and the sum of those P elements is divisible by M.

N can be upto 10^5

P can be upto 10^5

M can be upto 10

Elements in the array can be upto 10^9

What I thought: I thought of generating subset sum using dynamic programming starting from sum=M till sum=P*max(A) and then find all the subset sums which are divisible by M but it will surely be too unefficient. Any idea how can I solve this problem?

Subset sum (with repetition allowed) algorithm can be seen here: https://tutorialspoint.dev/algorithm/dynamic-programming-algorithms/ways-sum-n-using-array-elements-repetition-allowed

Even small hints about the approach would be appreciated

Upvotes: 2

Views: 593

Answers (1)

Adamos2468
Adamos2468

Reputation: 151

Hint: Usually in this kind of problems it's a good approach to check the constraints. One that gets the attention is the constraint for the variable M (up to 10). That means you can work with modular arithmetic and find the number of subset sums of size P that have a remainder 0 with M.

Upvotes: 1

Related Questions