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?

It seems work fine. Even assign `2^31-1` to `n`, it still take no more than 0.1 second with `g++ -std=c++14 -O2`. — yao99, Aug 08 '20 at 11:28
Does this answer your question? [Finding the number of digits of an integer](https://stackoverflow.com/questions/6655754/finding-the-number-of-digits-of-an-integer) — EvilTeach, Aug 08 '20 at 13:19
A function body with the same outcome as yours while being in O(1): `return n/9 + (n % 9 == 0 ? 0 : 1);` — Aziuth, Aug 08 '20 at 13:36
You need ```a = floor(n/9)``` nines, and the digit ```n-9a``` — Eliran Turgeman, Aug 08 '20 at 13:38
@EliranTurgeman An integer division does not need to be floored, it already is. — Aziuth, Aug 08 '20 at 13:39
Is there a condition like every digit should be used only once?? — Arun Kaliraja Baskaran, Aug 08 '20 at 14:15

score 7 · Accepted Answer · edited Aug 24 '20 at 14:43

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".)

score 6 · Answer 2 · edited Aug 24 '20 at 14:44

6

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;

edited Aug 24 '20 at 14:44

Peter Mortensen

30,738
21
105
131

answered Aug 08 '20 at 08:32

Ben

149
1
6

1

FYI: https://meta.stackoverflow.com/q/400125/430766 – bitmask Aug 08 '20 at 16:34
1

This answer shows more efficient code but doesn't explain the benefit of it. Yes, the code is shorter, but more importantly, it solves OP's efficiency problem that's causing the time limit exceeded (TLE) error by converting an O(n) loop to O(1) arithmetic operations and a branch. Code that fails a TLE doesn't "work fine"--it may be "correct but inefficient". – ggorlen Aug 08 '20 at 17:34

score 2 · Answer 3 · edited Aug 24 '20 at 14:56

Explanation

We know that every number a can be represented as (a_n * 10 ^ n) + ... + (a_2 * 10 ^ 2) + (a_1 * 10) + (a_0) where a_k are digits

and 10^n = 11...11 * 9 + 1 (n digits 1).

Meaning that number 10^n can be represented as the sum of 11...11 + 1 digits.

Now we can write a as (a_n * 11..11 * 9 + a_n) + ...

After grouping by 9 (help, I don't know English term for this. Factoring?) (a_n * 11..11 + a_n-1 * 11..11 + ... a_1) * 9 + (a_n + a_n-1 + ... + a_1 + a_0) Which I'll write as b_9 * 9 + b_1.

This means that number a can be represented as the sum of b_9 digits 9 + how much is needed for b_1 (this is recursive by the way)

To recapitulate:

Let's call function f

If -10 < digit < 10, the result is 1.
Two counters are needed, c1 and c2.
Iterate over digits
For every ith digit, multiply by i digit number 11..11 and add the result to c1
Add the ith digit to c2
The result is c_1 + f(c_2)

And for practice, implement this in a non-recursive way.

score 0 · Answer 4 · edited Aug 24 '20 at 14:53

As you guess, you need to iterate on a lower number to a bigger one, like 111119 is fine, but we want the lowest one... Your answer is wrong. The lowest would be 59!

You can brute force and it will work, but for a bigger number you will struggle, so you need to guess first: How many minimum digits do I need to find my solution?

For instance, if you want to find 42, just add as much 9 you need to overflow the result! 9 + 9 + 9 + 9 + 9 = 45. When you find the overflow, you know that the answer is lower than 99999.

Now how much do I need to decrease the value to get the correct answer, 3 as expected?

So 99996, 99969, etc... will be valid! But you want to lower, so you have to decrease the greatest unit (the left one of course!).

The answer would be 69999 = 42!

int n = 14;
int r = 0;

for (int i = i; i < 10 /*if you play with long or long long*/; i++)
   if (i * 9 >= n)
   {
       for (int j = 0; j < i; j++)
           r = r * 10 + 9;
       while (is_correct(r, n) == false)
       {
           // Code it yourself!!
       }
       return (r);
   }

Now it correctly returns true or false. You can make it return the number that r is actually a decrease what you need to decrease! It's not the fastest way possible, and there is always a faster way, with a binary shift, but this algorithm would work just fine!

Find minimum number of digits required to make a given number

4 Answers4

Explanation

To recapitulate: