สมมติว่าเรามีสตริงไบนารี S ที่มี n บิต ไม่มีศูนย์นำหน้าซ้ำซ้อน เราสามารถดำเนินการสองอย่างที่แตกต่างกันบน S -
-
สลับคู่ของบิตที่อยู่ติดกัน
-
แทนที่ "11" ทั้งหมดด้วย "1"
ให้ val(S) เป็นตัวแทนทศนิยมของ S เราต้องหาสตริงที่ถูกต้องขั้นต่ำ โดยที่ค่าสตริง A มีค่าน้อยกว่าสตริงที่ถูกต้อง 'B' เมื่อ val(A)
ดังนั้น หากอินพุตเป็น S ="1001" เอาต์พุตจะเป็น 100 เนื่องจากเราสามารถดำเนินการตามทฤษฎีได้ เช่น "1001" -> "1010" -> "1100" -> "100"
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -ขั้นตอน
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
ตัวอย่าง
#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;
} อินพุต
"1001"
ผลลัพธ์
100
