โปรแกรม C++ ค้นหาขั้นต่ำจำนวนการดำเนินการที่จำเป็นในการสร้างตัวเลข0

สมมติว่าเรามีสตริงตัวเลข S ที่มี n หลัก พิจารณา S แทนนาฬิกาดิจิทัล และสตริงทั้งหมดแสดงจำนวนเต็มตั้งแต่ 0 ถึง 10^n - 1 หากมีจำนวนหลักน้อยกว่า จะแสดง 0 นำหน้า ติดตามการดำเนินงาน -

ลดจำนวนนาฬิกาลง 1 หรือ
สลับสองหลัก

เราต้องการให้นาฬิกาแสดงค่า 0 พร้อมจำนวนการดำเนินการขั้นต่ำที่จำเป็น เราต้องนับจำนวนการดำเนินการที่จำเป็นในการทำเช่นนั้น

ดังนั้น หากอินพุตเป็น S ="1000" ผลลัพธ์จะเป็น 2 เนื่องจากเราสามารถสลับ 1 ตัวแรกกับ 0 ตัวสุดท้ายได้ ดังนั้นสตริงจะเป็น "0001" ตอนนี้ลดลง 1 เพื่อให้ได้ "0000"

ขั้นตอน

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

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"