Giả sử chúng ta có một chuỗi số S với n chữ số. Xét S đại diện cho một đồng hồ kỹ thuật số và toàn bộ chuỗi hiển thị một số nguyên từ 0 đến 10 ^ n - 1. Nếu có một số chữ số nhỏ hơn, nó sẽ hiển thị các số 0 đứng đầu. Thực hiện theo các hoạt động -
-
Giảm số trên đồng hồ đi 1 hoặc
-
Hoán đổi hai chữ số
Chúng tôi muốn đồng hồ sẽ hiển thị 0 với số lượng hoạt động tối thiểu cần thiết. Chúng tôi phải đếm số lượng hoạt động cần thiết để thực hiện điều đó.
Vì vậy, nếu đầu vào là S ="1000", thì đầu ra sẽ là 2, bởi vì chúng ta có thể hoán đổi 1 đầu tiên với 0 cuối cùng, vì vậy chuỗi sẽ là "0001" bây giờ giảm nó đi 1 để có "0000".
Các bước
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
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
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
#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;
} Đầu vào
"1000"
Đầu ra
2