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

Solution in Java

Implement a program to find out whether a number is divisible by the sum of its digits. Display appropriate messages.

class DivisibleBySum
{
     public static void main(String[] args) 
     {
        // Implement your code here 
        int num = 123;
        int number = num;
        int sum=0;
        for(;num>0;num /=10)
        {
            int rem = num % 10;
            sum += rem;
        }
        if(number %sum ==0)
           System.out.println(number+" is divisible by sum of its digits");
        else
           System.out.println(number+" is not divisible by sum of its digits");
    }
}

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.

Answer 3

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 4

The following approach should take about 10^7 operations per case.

Split numbers into a prefix (n/10000) and a suffix (n%10000). Once you choose a digit sum, only a little data from each of the prefix and suffix are needed to determine if the digit sum divides the number. (This is related to some things gnasher729 said, but I get a much different running time.)

For each possible digit sum d from 1 to 81,
    Map prefix p to a pair (p*10000 % d, digit sum(p)). 
    Tally the counts in a matrix M.
    Map each possible suffix s to a pair (s % d, digit sum(s)). 
    Tally the counts in a matrix N.
    For every (a,b), 
        total += M[a,b] *N[-a%d,d-b]

There are about 81 * (10^5 + 10^4) steps.

The edge cases where a prefix is partially allowed (L/10000, R/10000, and 100000) can be brute-forced in about 20000 steps once.

Answer 5

In the C code below, I have focused on the core portion, i.e. finding the DSD count. The code is admittedly ugly, but that's what you get when coding in a hurry.

The basic observation is that the digit sum can be simplified by tracking the digits of the number individually, reducing the digit sum determination to simple increments/decrements in each step. There are probably clever ways to accelerate the modulo computations, I could not come up with any on the double.

On my machine (Xeon E3 1270 v2, 3.5 GHz) the code below finds the count of DSDs in [1,1e9] in 3.54 seconds. I compiled with MSVC 2010 at optimization level -O2. While you stated a time limit of 1 second in an update to your question, it is not clear that this extreme case is exercised by the framework at the website you mentioned. In any event this will provide a reasonable baseline to compare other proposed solutions against.

#include <stdio.h>
#include <stdlib.h>

/* sum digits in decimal representation of x */
int digitsum (int x)
{
  int sum  = 0;
  while (x) {
    sum += x % 10;
    x = x / 10;
  }
  return sum;
}

/* split integer into individual decimal digits. p[0]=ones, p[1]=tens, ... */
void split (int a, int *p) 
{
  int i = 0;
  while (a) {
    p[i] = a % 10;
    a = a / 10;
    i++;
  }
}

/* return number of DSDs in [first,last] inclusive. first, last in [1,1e9] */
int count_dsd (int first, int last)
{
  int num, ds, count = 0, p[10] = {0};
  num = first;
  split (num, p);
  ds = digitsum (num);
  while (p[9] < 10) {
    while (p[8] < 10) {
      while (p[7] < 10) {
        while (p[6] < 10) {
          while (p[5] < 10) {
            while (p[4] < 10) {
              while (p[3] < 10) {
                while (p[2] < 10) {
                  while (p[1] < 10) {
                    while (p[0] < 10) {
                      count += ((num % ds) == 0);
                      if (num == last) {
                        return count;
                      }
                      num++;
                      p[0]++;
                      ds++;
                    }
                    p[0] = 0;
                    p[1]++;
                    ds -= 9;
                  }
                  p[1] = 0;
                  p[2]++;
                  ds -= 9;
                }
                p[2] = 0;
                p[3]++;
                ds -= 9;
              }
              p[3] = 0;
              p[4]++;
              ds -= 9;
            }
            p[4] = 0;
            p[5]++;
            ds -= 9;
          }
          p[5] = 0;
          p[6]++;
          ds -= 9;
        }
        p[6] = 0;
        p[7]++;
        ds -= 9;
      }
      p[7] = 0;
      p[8]++;
      ds -= 9;
    }
    p[8] = 0;
    p[9]++;
    ds -= 9;
  }  
  return count;
}

int main (void)
{
  int i, first, last, *count, testcases;
  scanf ("%d", &testcases);
  count = malloc (testcases * sizeof(count[0]));
  if (!count) return EXIT_FAILURE;
  for (i = 0; i < testcases; i++) {
    scanf ("%d %d", &first, &last);
    count[i] = count_dsd (first, last);
  }
  for (i = 0; i < testcases; i++) {
    printf ("%d\n", count[i]);
  }
  free (count);
  return EXIT_SUCCESS;
}

I copied the sample inputs stated in the question into a text file testdata, and when I call the executable like so:

dsd < testdata

the output is as desired:

4 10 9 33

Answer 6

Interesting problem. Straightforward solution would be to iterate through the numbers from L to R, calculate the sum of digits for each, and check for each whether the number is divisible by the sum of digits.

Calculating the sum of digits can be made faster obviously. The numbers xxx0, xxx1, xxx2, ..., xxx9 have digit sums n, n+1, n+2, ..., n+9. So for ten consecutive numbers almost no effort is needed to calculate the digit sum, just a modulo operation to check for divisibility.

The modulo check can be made faster. Compilers use clever tricks to divide by constants, replacing a slow division with a shift and a multiplication. You can search for how this is done, and since there are only 81 possible divisors, do at runtime what the compiler would do for constants. That should get the time down to few nanoseconds per number.

To do better: I'd make a loop checking for numbers with digit sum 1, digit sum 2, etc. As an example, assume I'm checking numbers with digit sum 17. These numbers must have a digit sum of 17, and also be multiples of 17. I take the numbers from 0000 to 9999 and for each I calculate the sum of digits, and the value modulo 17, and divide them into 37 x 17 sets where all the numbers in the set have the same digit sum and the same value modulo 17 and count the elements in each set.

Then to check the numbers from 0 to 9999: I pick the set where the digit sum is 17, and the value modulo 17 is 0 and take the element count of that set. To check numbers from 10,000 to 19,999: I pick the set where the digit sum is 16, and the value modulo 17 is 13 (because 10013 is divisible by 17), and so on.

That's just the idea. I think with a bit of cleverness that can be extended to a method that takes O (log^4 R) steps to handle all the numbers from L to R.