Return to Revisions

This should find the number in O(log(m)*log(m)). This is faster than O(i) which the OP uses.

static int sumOfDigits(long num) {
    int sum;
    // compute the sum as modulo 10 for each digit in num
    // T = O(log(num))
    for (sum = 0; num != 0; sum += num%10, num = num/10) { }
    return sum;
}

static int getNo() {
    long s = 9;
    while(sumOfDigits(s) <= n and s < m) {
      // O(log(n)) rounds each taking O(log(s)) => T = O(log(m)*log(m))
      s = s*10+9;
    }
    // s      = 99999... sumdigits(s) >= n
    // factor = 10000... same length as s
    // s is bigger than the wanted number 
    // and has a bigger sum than the wanted number has.
    // So now we just have to walk down towards the number.
    // We do that one decimal position at a time
    long factor = (s+1) / 10;

    while(factor != 0) {
      while(s - factor >= m and sumOfDigits(s - factor) >= n) {
        // we can subtract 1 from this decimal position
        // Max 10 rounds = O(1)*O(log(s))
        s -= factor;
      }
      // next decimal position
      // O(log(factor)) rounds => total: T = O(log(s)*log(factor))
      factor /= 10;
    }

    int i = s;
    if (sumOfDigits(i) == n) {
      ndigit = (Integer.toString(i)).length();
      return i;
    }
    return 0;
}