数を0にするために必要な最小の操作数を見つけるためのC++プログラム

n桁の数値文字列Sがあるとします。 Sがデジタル時計を表し、文字列全体が0から10 ^ n-1までの整数を示しているとします。桁数が少ない場合は、先頭に0が表示されます。操作に従ってください-

• 時計の数字を1つ減らす、または

• 2桁を入れ替える

必要な操作の最小数で時計が0を表示するようにします。そのために必要な操作の数を数える必要があります。

したがって、入力がS ="1000"の場合、最初の1を最後の0と交換できるため、出力は2になります。したがって、文字列は "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