Find minimum number of digits required to make a given number

Question

We have to find the minimum number of digits required to make a given number, for example: 14 => 95 (9 + 5 = 14) is two digits which is the minimum to form 14.

int moves(int n) {

    int m = 0;            // Minimum count

    while (n-9 >= 0) {    // To place maximum number of 9's
        n -= 9;
        m++;
    }

    if (n == 0) {         // If only nines made up the number
        return m;
    }

    else {
        m++;
        return m;
    }
}

I am getting a TLE (runtime time limit exceeded) by an online judge. How can I improve it or is there a better approach?

Answer 1

Your code starts by looking at how many times 9 fits into that number. This can be done way more easily:

int m = n/9;

This suffices since we do an integer division, in which the remainder is thrown away. Note that if n would be float or another floating type, this would not work.

The question left is if it is divisible by 9 or not. If not, we have one additional digit. This can be done by the modulo operator (made it verbose for ease of understanding):

bool divisible_by_nine = (n % 9 == 0);

Assuming that you might not know the modulo operator, it returns the remainder of an integer division, 47 % 9 = 2 since 47 / 9 = 5 remainder 2.

Without it, you would go with

int remainder = n - 9*m;
bool divisible = (remainder == 0);

Combined:

int required_digits(int number)
{
   bool divisible = (number % 9 == 0);
   return number/9 + (divisible ? 0 : 1);
}

Or in a single line, depending on how verbose you want it to be:

int required_digits(int number)
{
   return number/9 + (number % 9 == 0 ? 0 : 1);
}

Since there isn't any loop, this is in Θ(1) and thus should work in your required time limit.

(Technically, the processor might as well handle the division somewhat like you did internally, but it is very efficient at that. To be absolutely correct, I'd have to add "assuming that division is a constant time operation".)

Answer 2

Your solution works fine. You can try the shorter:

return (n%9==0)? n/9 : n/9 +1 ;

Shorter, but less easy to read...

Or a compromise:

if (n%9==0) // n can be divided by 9
   return n/9;
else
   return n/9+1;