Sum of digits in a subset of a set

Question

I have a set S like this [00 01 10 11] and an element E as 11. I want to find out the number of subsets of this set whose sum of digits is greater than or equal to the sum of digits of the element E.

For example in this case the answer is 10. The 10 sets satisfying the constraints are :

00 01 10 11 // Sum is 3 which is greater than 2 (sum of digits of E)
00 01 11 
00 10 11
01 10 11
00 11
01 11
10 11
11
00 01 10
01 10

The sum of all the digits of the above subsets is greater than or equal to 2 (sum of digits of E).

I tried the following

public static void main(String[] args) {
    Set<String> inputSet = new HashSet<String>();
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    int M = sc.nextInt();// specifies the length of the digts in the set.
    for (long i = 0 ; i < N; i++) {
        inputSet.add(sc.next());
    }
    long sum = 0;
    String E = sc.next();//
    sc.close();
    for (String str : E.split("(?!^)")) {
        sum = sum + Integer.parseInt(str);
    }
    List<Set<String>> subSets = new ArrayList<Set<String>>();
    for (String addToSets : inputSet) {
        List<Set<String>> newSets = new ArrayList<Set<String>>();
        for (Set<String> curSet : subSets) {
            Set<String> copyPlusNew = new HashSet<String>();
            copyPlusNew.addAll(curSet);
            copyPlusNew.add(addToSets);
            newSets.add(copyPlusNew);
        }
        Set<String> newValSet = new HashSet<String>();
        newValSet.add(addToSets);
        newSets.add(newValSet);
        subSets.addAll(newSets);
    }
    long sum1;
    long count = 0;
    for (Set<String> set : subSets) {
        sum1 = 0;
        for (String setEntry : set) {
            for (String s : setEntry.split("(?!^)")){
                sum1 = sum1 + Integer.parseInt(s);
            }
        }
        if (sum == sum1 || sum1 > sum)
            count = count+1;
    }
    System.out.println(count);
}

Constraints 1 <= N <= 10^5

1 <= M <= 20

The above approach won't work for the size of sets of the range 10⁵. Please help providing an efficient approach for this. Thanks!

Answer 1

The catch in solving this question is just remembering that addition is associative. So when you add those digits does not really matter. So if we reduce this to a known problem, it's easy to solve this.

Convert your input array to sum of digits array. That is if your original array is A, then the relation with your resulting array B will be:

          B[i] = sum of digits of(A[i]).

Say K is sum of digits(E)

Then your problem reduces to

     Find number of subsets in B whose sum is <= K

Which is easy.

EDIT:

  public static void main(String[] args) {
    int[] A ={01,11,111};
    int B[] = new int[A.length];
    for(int i=0;i<A.length;i++){
        B[i]=getDigitSum(A[i]);
    }
     int E = 11;
    int K= getDigitSum(E);
    int N =B.length;
    Arrays.sort(B);
    int DP[][] = new int[B.length][B[B.length-1]+1];


    for (int i=0;i<N;i++) {
        DP[i][B[i]] = 1;

        if (i == 0) continue;

        for (int k=0;k<K;k++) {
            DP[i][k] += DP[i - 1][k];
        }
        for (int k=0;k<K;k++) {
            if( k + B[i] >= K) break ;
            DP[i][k + B[i]] += DP[i - 1][k];
        }
    }
    int sum=0;
    for(int i=0;i<K;i++) {
        sum = sum +DP[N-1][i];
    }
    int result = ((int)Math.pow(2,N)) - sum-1;
    System.out.println(result);

}

private static int getDigitSum(int num) {
    int sum =0;
    while(num >0){
       sum=sum+ (num%10);
        num= num/10;
    }
    return sum;
}