Giả sử chúng ta có một chuỗi nhị phân S với n bit. Không có số 0 ở đầu dư thừa. Chúng tôi có thể thực hiện hai hoạt động khác nhau trên S -
-
Hoán đổi bất kỳ cặp bit nào liền kề
-
Thay thế tất cả "11" bằng "1"
Gọi val (S) là biểu diễn thập phân của S. Chúng ta phải tìm chuỗi đúng nhỏ nhất, trong đó chuỗi đúng A nhỏ hơn chuỗi đúng khác 'B' khi val (A)
Vì vậy, nếu đầu vào là S ="1001", thì đầu ra sẽ là 100, vì chúng ta có thể thực hiện phép toán như "1001" -> "1010" -> "1100" -> "100".
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 res := a blank string res := res + S[0] for initialize i := 1, when i < n, update (increase i by 1), do: if S[i] is same as '0', then: res := res concatenate "0" return res
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; string solve(string S){ int n = S.size(); string res = ""; res += S[0]; for (int i = 1; i < n; i++){ if (S[i] == '0'){ res += "0"; } } return res; } int main(){ string S = "1001"; cout << solve(S) << endl; }
Đầu vào
"1001"
Đầu ra
100