Trong bài toán này, chúng ta được cung cấp một chuỗi có thể được hiểu là một số. Bây giờ chúng ta phải thực hiện phân vùng chuỗi đó thành hai phần sao cho phần đầu tiên chia hết cho A và phần thứ hai chia hết cho B (hai số nguyên cho trước). Ví dụ -
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
Bây giờ trong bài toán này, chúng tôi sẽ thực hiện một số tính toán trước để làm cho chương trình của chúng tôi nhanh hơn và sau đó nó sẽ có thể hoạt động trên các ràng buộc cao hơn.
Phương pháp tiếp cận để tìm giải pháp
Trong cách tiếp cận này, chúng tôi sẽ chạy hai vòng qua chuỗi, đầu tiên từ đầu đến cuối và vòng thứ hai từ cuối đến đầu. Bây giờ tại mọi thời điểm, chúng tôi lấy mod của số nguyên được tạo thành với an trong vòng lặp đầu tiên và với b trong vòng lặp thứ hai, và sau đó chúng tôi có thể tìm thấy câu trả lời của mình.
Ví dụ
#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;
} Đầu ra
YES 12 3
Giải thích về Quy tắc trên
Trong cách tiếp cận này, chúng tôi tính toán phần còn lại của số được hình thành tại mọi phép chia bây giờ. Số đầu tiên của chúng ta sẽ chia hết cho a, vì vậy chúng ta chạy một vòng lặp về phía trước và lưu trữ mod của số đó với a. Với b, chúng ta chạy một vòng lặp lùi và lưu trữ các mod ngay bây giờ vì chúng ta biết rằng nếu mod của chúng ta với an ở bất kỳ vị trí nào là 0 và mod với b có chỉ số tiếp theo là 0, đó sẽ là câu trả lời của chúng ta và do đó chúng ta in nó.
Kết luận
Trong hướng dẫn này, chúng tôi giải quyết một vấn đề để tìm Phân chia một số thành hai phần có thể chia được. Chúng tôi cũng đã học chương trình C ++ cho vấn đề này và cách tiếp cận hoàn chỉnh (Bình thường) mà chúng tôi đã giải quyết vấn đề này. Chúng ta có thể viết cùng một chương trình bằng các ngôn ngữ khác như C, java, python và các ngôn ngữ khác. Chúng tôi hy vọng bạn thấy hướng dẫn này hữu ích.