I am working on the following problem:
Given a set of non-negative distinct integers, and a value m, determine if there is a subset of the given set with sum divisible by m.
Input: The first line of input contains an integer T denoting the number of test cases. Then T test cases follow. The first line of each test case contains an integer N and M where N denotes the size of the array and M is the number for which we have to check the divisibility. The second line of each test case contains N space separated integers denoting elements of the array A[ ].
Output: If there is a subset which is divisible by M print '1' else print '0'.
I have tried a recursive solution:
#include <iostream>
#include<unordered_map>
using namespace std;
bool find_it(int a[],int &m,int n,int sum) {
if ((sum%m)==0 && sum>0)
return true;
if (n==0)
return false;
return find_it(a,m,n-1,sum) || find_it(a,m,n-1,sum-a[n-1]);
}
int main() {
int tc;
cin >> tc;
while (tc--) {
int n,m;
cin >> n >> m;
int a[n];
int sum = 0;
for (int i=0;i<n;i++) {
cin >> a[i];
sum += a[i];
}
bool answer = find_it(a,m,n,sum);
cout << answer << "\n";
}
return 0;
}
Which works fine and get accepted, but then I tried top-down approach, and am getting TLE ("Time Limit Exceeded"). What am I doing wrong in this memoization?
#include <iostream>
#include<unordered_map>
using namespace std;
bool find_it(
int a[], int &m, int n, int sum,
unordered_map<int,unordered_map<int,bool>> &value,
unordered_map<int,unordered_map<int,bool>> &visited){
if ((sum%m)==0 && sum>0)
return true;
if(n==0)
return false;
if(visited[n][sum]==true)
return value[n][sum];
bool first = false,second = false;
first = find_it(a,m,n-1,su1m,value,visited);
if(sum<a[n-1])
{
second=false;
}
else
second = find_it(a,m,n-1,sum-a[n-1],value,visited);
visited[n][sum] = true;
value[n][sum] = first || second;
return value[n][sum];
}
int main() {
int tc;
cin >> tc;
while (tc--) {
int n,m;
cin >> n >> m;
int a[n];
int sum = 0;
for (int i=0;i<n;i++) {
cin >> a[i];
sum+=a[i];
}
unordered_map<int,unordered_map<int,bool>> value;
unordered_map<int,unordered_map<int,bool>> visited;
cout << find_it(a,m,n,sum,value,visited) << "\n";
}
return 0;
}
Well, at first, you can reduce the problem to a modulo m
problem, as properties of integers don't change when switching to modulo m
field. It's easy to demonstrate that being divisible by m
is the same as being identical to 0
mod m
.
I would first convert all those numbers to their counterparts modulo m
and eliminate repetitions by considering a_i
, 2*a_i
, 3*a_i
,... until rep_a_i * a_i
, all of them mod m
. Finally you get a reduced set that has at most m
elements. Then eliminate all the zeros there, as they don't contribute to the sum. This is important for two reasons:
O(a^n)
into a O(K)
problem, as its complexity doesn't depend on the number of elements of the set, but the number m
.a_i
follow a geometric sequence with K > 2
)The rest of the problem is a Knapsack problem (which is NP-complete) or one of it's P variants.
In case you don't get so far (cannot reduce it to an easy-knapsack problem) then you have to reduce the number of a_i
's so the exponential time gets a minimum exponent :)
(@mss asks for elaboration in a comment) Assume you have m = 8
and the list is 1 2 4 6 12 14 22
. After reduction mod m
the list remains as: 1 2 4 6 4 6 6
in which 6 is repeated three times. we must consider the three possible repetitions of 6, as they can contribute to get a sum, but not more (for the moment), let's consider 6*1 = 6
, 6*2 = 12
and 6*3 = 18
, the first is the original 6
, the second makes a third repetition of 4
(so we'll need to consider 3 4
s in the list), and the third converts into a 2
. So now, we have 1 2 4 6 4 4 2
in the list. We make the same for the 4
repetitions (two 4
run into 8
which is 0
mod m
and don't contribute to sums, but we have to keep one such 0
because this means you got by repeated numbers the target m
) getting into 1 2 4 6 0 4 2
=> 1 2 4 6 0 0 2
=(reorder)=> 0 1 2 2 4 6
=> 0 1 2 4 6
. This should be the final list to consider. As it has a 0
, you know a priori that there's one such sum (in this case you got is as including the two 4
, for the original list's 4
and 12
numbers.