Programme C++ pour trouver le nombre minimum d'opérations nécessaires pour créer un nombre 0

Supposons que nous ayons une chaîne numérique S contenant n chiffres. Supposons que S représente une horloge numérique et que la chaîne entière affiche des nombres entiers de 0 à 10^n - 1. S'il y a moins de chiffres, des 0 en tête sont affichés. Suivez ces étapes -

• décrémentez le nombre sur l'horloge de 1, ou

• échangez les deux chiffres p>

Nous voulons que l'horloge affiche 0 avec le nombre minimum d'opérations. Nous devons calculer le nombre d'opérations nécessaires pour réaliser cette opération.

Donc, si l'entrée est quelque chose comme S = "1000", la sortie sera 2 car nous pouvons échanger le premier 1 avec le dernier 0 donc la chaîne sera "0001", soustrayez maintenant 1 pour obtenir "0000".

Étapes

Pour résoudre ce problème, nous suivrons les étapes suivantes -

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 &#39;0&#39;, then:
      x := x + (digit at place S[i]) + 1
return x

Exemple

Voyons l'implémentation suivante pour une meilleure compréhension -

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

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

Input

"1000"

Output

2

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!