首页 > 文章列表 > C++程序以找到使数字为0所需的最少操作次数

C++程序以找到使数字为0所需的最少操作次数

c语言 数字 操作次数
369 2023-08-28

假设我们有一个包含 n 位数字的数字字符串 S。假设 S 代表一个数字时钟,整个字符串显示从 0 到 10^n - 1 的整数。如果位数较少,则会显示前导 0。按照以下操作 -

  • 将时钟上的数字减 1,或

  • 交换两位数字

我们希望时钟能够以最少的操作次数显示 0。我们必须计算完成此操作所需的操作数。

因此,如果输入类似于 S = "1000",则输出将为 2,因为我们可以将前 1 与后 0 交换,所以字符串将是“0001”,现在将其减 1 得到“0000”。

步骤

为了解决这个问题,我们将按照以下步骤操作 -

n := size of S
x := digit at place S[n - 1]
for initialize i := 0, when i <= n - 2, update (increase i by 1), do:
   if S[i] is not equal to '0', then:
      x := x + (digit at place S[i]) + 1
return x

示例

让我们看看以下实现,以便更好地理解 -

#include <bits/stdc++.h>
using namespace std;

int solve(string S) {
   int n = S.size();
   int x = S[n - 1] - '0';
   for (int i = 0; i <= n - 2; i++)
      if (S[i] != '0')
         x = x + S[i] + 1 - '0';
   return x;
}
int main() {
   string S = "1000";
   cout << solve(S) << endl;
}

输入

"1000"

输出

2