ในปัญหานี้ เราได้รับสตริงที่สามารถตีความว่าเป็นตัวเลขได้ ตอนนี้ เราต้องดำเนินการแบ่งพาร์ติชันที่สตริงออกเป็นสองส่วน โดยที่ส่วนแรกหารด้วย A และส่วนที่สองหารด้วย B ลงตัว (จำนวนเต็มสองจำนวนที่มอบให้เรา) ตัวอย่างเช่น −
Input : str = "123", a = 12, b = 3 Output : YES 12 3 "12" is divisible by a and "3" is divisible by b. Input : str = "1200", a = 4, b = 3 Output : YES 12 00 Input : str = "125", a = 12, b = 3 Output : NO
ในปัญหานี้ เราจะทำการคำนวณล่วงหน้าซึ่งจะทำให้โปรแกรมของเราเร็วขึ้น และจากนั้นจะสามารถทำงานในข้อจำกัดที่สูงขึ้นได้
แนวทางในการหาแนวทางแก้ไข
ในแนวทางนี้ เราจะรันสองลูปผ่านสตริง ครั้งแรกตั้งแต่ต้นจนจบ และลูปที่สองตั้งแต่ต้นจนจบ ในทุกจุด เราจะนำ mod ของจำนวนเต็มที่สร้างด้วย a ในลูปแรกและ b ในลูปที่สอง จากนั้นเราจะหาคำตอบได้
ตัวอย่าง
#include <bits/stdc++.h>
using namespace std;
void divisionOfString(string &str, int a, int b){
int n = str.length();
vector<int> mod_a(n+1, 0); //
mod_a[0] = (str[0] - '0')%a;
for (int i=1; i<n; i++) // front loop for calculating the mod of integer with a
mod_a[i] = ((mod_a[i-1]*10)%a + (str[i]-'0'))%a;
vector<int> mod_b(n+1, 0);
mod_b[n-1] = (str[n-1] - '0')%b;
int power10 = 10; // as we have assigned answer to last index
for (int i= n-2; i>=0; i--){ // end loop for calculating the mod of integer with b
mod_b[i] = (mod_b[i+1] + (str[i]-'0')*power10)%b;
power10 = (power10 * 10) % b;
}
for (int i=0; i<n-1; i++){ // finding the division point
if (mod_a[i] != 0) // we can skip through all the positions where mod_a is not zero
continue;
if (mod_b[i+1] == 0){ // now if the next index of mod_b is also zero so that is our division point
cout << "YES\n";
/*******Printing the partitions formed**********/
for (int k=0; k<=i; k++)
cout << str[k];
cout << " ";
for (int k=i+1; k < n; k++)
cout << str[k];
return;
}
}
cout << "NO\n"; // else we print NO
}
// Driver code
int main(){
string str = "123"; // given string
int a = 12, b = 3;
divisionOfString(str, a, b);
return 0;
} ผลลัพธ์
YES 12 3
คำอธิบายของโค้ดด้านบน
ในแนวทางนี้ เราคำนวณส่วนที่เหลือของจำนวนที่เกิดขึ้นในทุกดิวิชั่นแล้ว ตัวเลขตัวแรกของเราควรจะหารด้วย a ลงตัว ดังนั้นเราจึงรันลูปไปข้างหน้าและเก็บ mod ของตัวเลขนั้นด้วย a ด้วย b เราเรียกใช้การวนซ้ำย้อนกลับและจัดเก็บ mods ในตอนนี้ เนื่องจากเราทราบว่าหาก mod ของเราที่ตำแหน่งใดๆ เป็นศูนย์ และ mod ที่มี b ที่มีดัชนีถัดไปเป็นศูนย์ นั่นจะเป็นคำตอบของเรา และด้วยเหตุนี้เราจึงพิมพ์ออกมา
บทสรุป
ในบทช่วยสอนนี้ เราจะแก้ปัญหาเพื่อค้นหาหมายเลขพาร์ติชั่นออกเป็นสองส่วนที่แบ่งได้ นอกจากนี้เรายังได้เรียนรู้โปรแกรม C++ สำหรับปัญหานี้และแนวทางที่สมบูรณ์ (ปกติ) ซึ่งเราแก้ไขปัญหานี้ เราสามารถเขียนโปรแกรมเดียวกันในภาษาอื่นๆ เช่น C, java, python และภาษาอื่นๆ เราหวังว่าคุณจะพบว่าบทช่วยสอนนี้มีประโยชน์
