c++ - 找出构成给定数字所需的最少位数

Question

我们必须找到构成给定数字所需的最少位数，例如:14 => 95 (9 + 5 = 14) 是两位数，这是构成 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;
    }
}

我收到了在线评委的 TLE(超出运行时间限制)。我该如何改进它或者有更好的方法？

Answer 1

您的代码首先查看 9 适合该数字的次数。这可以更轻松地完成:

int m = n/9;

这足够了，因为我们进行了整数除法，其中余数被丢弃。请注意，如果 n将是 float或其他 float 类型，这是行不通的。
剩下的问题是它是否能被 9 整除。如果没有，我们还有一位额外的数字。这可以通过模运算符来完成(为了便于理解，它变得冗长):

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

假设您可能不知道模运算符，它返回整数除法的余数，47 % 9 = 2 因为 47/9 = 5 余数 2。
没有它，你会去

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

综合:

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

或者在一行中，具体取决于您希望它的详细程度:

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

由于没有任何循环，这是在 Θ(1) 中，因此应该在您所需的时间限制内工作。
(从技术上讲，处理器可能会像您在内部那样处理除法，但在这方面非常有效。要绝对正确，我必须添加“假设除法是恒定时间操作”。)