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

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或其他浮动类型，这将不起作用。

剩下的问题是它是否能被 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) 中，因此应该在您要求的时间限制内工作。

（从技术上讲，处理器可能会像您在内部那样处理除法，但在这方面非常有效。要绝对正确，我必须添加“假设除法是恒定时间操作”。）

Answer 2

您的解决方案工作正常。您可以尝试较短的：

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

更短，但不太容易阅读......

或者妥协：

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