Sum of digits in a subset of a set
I have a set S like this [00 01 10 11]
and an element E like 11
. I want to know the number of subsets of this set whose sum of digits is greater than or equal to the sum of digits of E.
For example, in this case the answer is 10.10 sets satisfying the constraints:
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 digits in the above subsets is greater than or equal to 2 (sum of E digits).
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 a range set size of 10 5 . Please help provide an efficient approach for this. Thank!
source to share
The trap in solving this question is simply remembering what addition is associative
. So when you add these numbers, it doesn't really matter. Therefore, if we reduce this to a known issue, it is easy to fix this issue.
Convert the input array to sum of digits array
. That is, if your original array is A, then the relationship to your resulting array B would be:
B[i] = sum of digits of(A[i]).
Say K sum of digits(E)
Then your problem boils down to
Find number of subsets in B whose sum is <= K
It's 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;
}
source to share