So I’m working on this problem, and here’s my code:
public final class SubmultiplesOfN {
private static final int MOD = (int) 1e9 + 7;
public static void main(String[] args) {
System.out.println(count("123456789012345678901234567890", 1));
}
public static int count(String num, int div) {
long[][] modSubseqNum = new long[num.length()][div];
modSubseqNum[0][Character.getNumericValue(num.charAt(0)) % div] = 1;
for (int i = 0; i < num.length() - 1; i++) {
int nextDig = Character.getNumericValue(num.charAt(i + 1));
if (nextDig == -1 || nextDig == -2) {
throw new IllegalArgumentException("invalid number given for argument num");
}
modSubseqNum[i + 1][nextDig % div] += nextDig != 0 ? 1 : 0;
for (int m = 0; m < div; m++) {
int nextMod = (10 * m + nextDig) % div;
modSubseqNum[i + 1][nextMod] = (modSubseqNum[i + 1][nextMod] + modSubseqNum[i][m]) % MOD;
modSubseqNum[i + 1][m] = (modSubseqNum[i + 1][m] + modSubseqNum[i][m]) % MOD;
}
}
return (int) modSubseqNum[num.length() - 1][0];
}
}
The problem is, it doesn’t account for duplicates. I tried using the technique described here to account for duplicates, but that doesn’t seem to work with this problem.
So how do I make the code account for duplicates?