How to count the numbers that are divisible by their sum of digits?

Question

Following is a question from hackerearth. here's the link to the problem problem! I coded its solution in java and c but got time limit exceeded for some test cases on submission. No participant was able to solve this for all test cases. What is the most efficient solution for this?

QUESTION:

Bob likes DSD Numbers. DSD Number is a number which is divisible by its Digit Sum in Decimal Representation.

digitSum(n) : Sum of digits of n (in Decimal Representation)

eg: n = 1234 then digitSum(n) = 1 + 2 + 3 + 4 = 10

DSD Number is number n such that n % digitSum(n) equal to 0

Bob asked Alice to tell the number of DSD Numbers in range [L,R] inclusive.

Constraints:

1 <= test cases <= 50

1<=L<=R<=10^9

Sample Input

4
2 5
1 10
20 45
1 100

Sample Output

4
10
9
33

Code in Java:

class DSD {

public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new    InputStreamReader(System.in));
    PrintWriter out=new PrintWriter(System.out);
    int t=Integer.parseInt(br.readLine());
    while(t-->0){
    StringTokenizer st=new StringTokenizer(br.readLine());
    int L=Integer.parseInt(st.nextToken());
    int R=Integer.parseInt(st.nextToken());

    int count=0,sum=0,i=L,j=0;

    while(i>0){
    sum+=i%10;
    i=i/10;
    }
    if(L%sum==0)
        count++;
    for(i=L+1;i<=R;i++){
    if(i%10!=0){
    sum+=1;
    }
    else
    {
    j=i;
    while(j%10==0){
    sum-=9;
    j/=10;
    }
    sum+=1;
    }
    if(i%sum==0)
        count++;
    }
        out.println(count);
    }
    out.close();
} 
}

Answer 1

We can solve this problem by using dynamic programming.

Observation:

• There will be maximum 10 digits for each number, so the maximum sum of digit for each number will be less than 100.

So, assuming that we know the sum of digit for one number, by processing digit by digit, we have four things to check:

• Whether the current number is larger than the lower bound.
• Whether the current number is smaller than the upper bound.
• What is the mod of current number with its sum.
• What is the current sum of all digits.

We come up with this function int count(int digit, boolean larger, boolean smaller, int left, int mod), and then, the dp state: dp[digit][larger][smaller][left][mod].

For each test case, time complexity is number of possible sum^3 x number of digit = 100^3*10 = 10^7.

There is 50 test cases -> 50*10^7 = 5*10^8 operations, which still be in the time limit.

Java code:

static int[][][][][] dp;
static int[][][][][] check;
static int cur = 0;

public static void main(String[] args) throws FileNotFoundException {
    // PrintWriter out = new PrintWriter(new FileOutputStream(new File(
    // "output.txt")));
    PrintWriter out = new PrintWriter(System.out);
    Scanner in = new Scanner();


    int n = in.nextInt();
    dp = new int[11][2][2][82][82];
    check = new int[11][2][2][82][82];
    for (int i = 0; i < n; i++) {

        int l = in.nextInt();
        int r = in.nextInt();
        String L = "" + l;
        String R = "" + r;
        while (L.length() < R.length()) {
            L = "0" + L;
        }
        int result = 0;
        for (int j = 1; j <= 81; j++) {

            cur = cur + 1;
            result += count(0, 0, 0, j, 0, j, L, R);
        }
        out.println(result);
    }
    out.close();
}

public static int count(int index, int larger, int smaller, int left,
        int mod, int sum, String L, String R) {
    if (index == L.length()) {
        if (left == 0 && mod == 0) {
            return 1;
        }
        return 0;
    }
    if((L.length() - index) * 9 < left){
        return 0;
    }
    if (check[index][larger][smaller][left][mod] == cur) {
        return dp[index][larger][smaller][left][mod];
    }
    //System.out.println(cur);
    check[index][larger][smaller][left][mod] = cur;
    int x = L.charAt(index) - '0';
    int y = R.charAt(index) - '0';
    int result = 0;
    for (int i = 0; i < 10 && i <= left; i++) {

        if (x > i && larger == 0) {
            continue;
        }
        if (y < i && smaller == 0) {
            continue;
        }
        int nxtLarger = larger;
        int nxtSmaller = smaller;
        if (x < i) {
            nxtLarger = 1;
        }
        if (y > i) {
            nxtSmaller = 1;
        }
        int nxtMod = (mod * 10 + i) % sum;
        result += count(index + 1, nxtLarger, nxtSmaller, left - i, nxtMod,
                sum, L, R);
    }
    return dp[index][larger][smaller][left][mod] = result;
}

Update: I have submitted and passed all the test cases for this problem, (2nd person who solved this) This is the link of my submission

Answer 2

Let f (L, R) = "number of integers L ≤ x ≤ R where x is divisible by the sum of its digits". We define that x = 0 is not counted.

Let g (M) = "number of integers 1 ≤ x < M where x is divisible by the sum of its digits". We have f (L, R) = g (R + 1) - g (L).

Find the largest k ≥ 0 such that 10^k <= M. Find the largest a ≥ 1 such that a * 10^k <= M. All integers < M have at most 9k + (a-1) as sum of digits.

Let h (M, n) = "number of integers 1 ≤ x < M where x is divisible by n, and the sum of digits is n". g (M) is the sum of h (M, n) for 1 ≤ n ≤ 9*k + (a - 1).

Let r (a, k, n) = "number of integers a*10^k ≤ x < (a+1)*10^k where x is divisible by n, and the sum of digits is n". h (M, n) can be calculated by adding values of r (a, k, n) in an obvious way; for example:

h (1,234,000,000, n) = r (0, 9, n) + r (10, 8, n) + r (11, 8, n) + r (120, 7, n) + r (121, 7, n) + r (122, 7, n) + r (1230, 6, n) + r (1231, 6, n) + r (1232, 6, n) + r (1233, 6, n).

Let f (k, n, d, m) = "number of integers 0 ≤ x < 10^k where the sum of digits is d, and x % n = m". We can calculate r (a, k, n) using this function: The last k digits must have a digit sum of n - digitsum (a). If the whole number is divisible by n, then the last k digits must have a remainder of (- a*10^k) % n. So r (a, k, n) = f (k, n, n - digitsum(a), - (a*10^k) % n).

f (k, n, d, m) is trivial if k = 1: Only for the number d is the sum of digits equal to d, so f (1, n, d, m) is 1 if d % n = m, and 0 otherwise.

To calculate f (k+1, n, d, m) we add f (k, n, d-a, (m - a*10^k)%n) for 0 ≤ a ≤ 9. Obviously all the values f (k, n, d, m) must be stored so they are not recalculated again and again.

And that's it. How many operations: If R < 10^r, then numbers have up to 9r digits. We calculate values f (k, n, d, m) for 1 ≤ k ≤ r, for 1 ≤ n ≤ 9r, for 0 ≤ d ≤ 9r, for 0 ≤ m < n. For each of those we add 10 different numbers, so we have less than 10,000 r^4 additions. So numbers up to 10^19 are no problem.