Return to Answer

This should find the number in O(log(i)*log(i)). 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;
}

This should find the number in O(log(i)*log(i)). This is faster than O(i) which the OP uses and thus improves run time (as asked for "I would love to know how to increase it's efficiency").

It uses long instead of int converted to string.

Only 2 methods and around 10 lines of code are changed. The rest of the code remains the same and it therefore not included here.

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 && 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 && 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;
    // Below same as original code.
    if (sumOfDigits(i) == n) {
      ndigit = (Integer.toString(i)).length();
      return i;
    }
    return 0;
}

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;
}

This should find the number in O(log(i)*log(i)). 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;
}

This should find the number in O(log(i)*log(i)).

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

static int getNo() {
    long s = 9;
    while(sumOfDigits(s) <= n and s < 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
        s -= factor;
      }
      // next decimal position
      factor /= 10;
    }

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

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;
}