मान लीजिए कि हमारे पास n अंकों के साथ एक संख्यात्मक स्ट्रिंग S है। मान लें कि S एक डिजिटल घड़ी का प्रतिनिधित्व करता है और पूरी स्ट्रिंग 0 से 10^n - 1 तक एक पूर्णांक दिखाती है। यदि अंकों की एक छोटी संख्या है, तो यह अग्रणी 0s दिखाएगा। संचालन का पालन करें -
-
घड़ी पर संख्या 1 से घटाएं, या
-
दो अंकों की अदला-बदली करें
हम चाहते हैं कि घड़ी 0 दिखाएगी जिसमें न्यूनतम संख्या में संचालन की आवश्यकता होगी। हमें ऐसा करने के लिए आवश्यक कार्यों की संख्या गिननी होगी।
इसलिए, यदि इनपुट S ="1000" जैसा है, तो आउटपुट 2 होगा, क्योंकि हम पहले 1 को अंतिम 0 के साथ स्वैप कर सकते हैं, इसलिए स्ट्रिंग "0001" होगी अब इसे "0000" प्राप्त करने के लिए 1 से घटाएं।
कदम
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
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