Một chuỗi 0-9 được đưa ra. Đối với bài toán này, chúng ta cần tính số chuỗi chia hết cho 8 và không chia hết cho 3. Đây là bài toán 2 bước và chúng ta cần thực hiện mã từng bước một để giải nó, chẳng hạn
Đầu vào
str = "80"
Đầu ra
2
Đầu vào
str = "7675636788"
Đầu ra
15
Phương pháp tiếp cận để tìm giải pháp
Chỉ những số có 3 chữ số tận cùng mới chia hết cho 8 và tổng các chữ số chia hết cho 3 mới chia hết cho 8.
Bây giờ lưu trữ tổng tiền tố của chuỗi sao cho tổng các chữ số của mô-đun tiền tố 3 là 0,1 hoặc 2. Sau đó, chuỗi được lặp lại cho tất cả các vị trí của i. Sau đó đếm số chuỗi con tại i chia hết cho 8 — bây giờ, trừ số chuỗi con tại i, chúng chia hết cho 3 từ giá trị này.
| S | Mảng 2D kích thước X 3 được xác định, | S | là kích thước của một chuỗi, giả sử dp [i] [j].
Tại bất kỳ chỉ mục nào tôi dp [i] [j]. Bắt đầu từ chỉ số i đến 0, số chuỗi con có đầu ra j. Vì vậy, 0 <=j <=0, kể từ mô-đun 3.
Chúng ta cần lặp lại chuỗi để kiểm tra xem các số có một chữ số, hai chữ số và ba chữ số có chia hết cho 8.
-
Để xác định xem một ký tự có là 8 ở chỉ mục hay không, hãy kiểm tra số ở chỉ mục.
-
Chia số cho 8 thay cho 3 nếu có hai chữ số.
Giả sử số đó chia hết cho 8. Phải có hai (1-3) chuỗi con nếu nó chia hết cho 8. Tuy nhiên, nó cũng sẽ có các chuỗi con chia hết cho 8. Để loại bỏ chúng.
Ví dụ
#include <bits/stdc++.h>
using namespace std;
#define MAX 1000
int count (char s[], int len) {
int cur = 0,
dig = 0;
int sum[MAX], dp[MAX][3];
memset (sum, 0, sizeof (sum));
memset (dp, 0, sizeof (dp));
dp[0][0] = 1;
for (int i = 1; i <= len; i++) {
dig = int (s[i - 1]) - 48;
cur += dig;
cur %= 3;
sum[i] = cur;
dp[i][0] = dp[i - 1][0];
dp[i][1] = dp[i - 1][1];
dp[i][2] = dp[i - 1][2];
dp[i][sum[i]]++;
}
int ans = 0, dprev = 0, value = 0, dprev2 = 0;
for (int i = 1; i <= len; i++) {
dig = int (s[i - 1]) - 48;
if (dig == 8) ans++;
if (i - 2 >= 0) {
dprev = int (s[i - 2]) - 48;
value = dprev * 10 + dig;
if ((value % 8 == 0) && (value % 3 != 0)) ans++;
}
// Taking 3 digit number.
if (i - 3 >= 0){
dprev2 = int (s[i - 3]) - 48;
dprev = int (s[i - 2]) - 48;
value = dprev2 * 100 + dprev * 10 + dig;
if (value % 8 != 0) continue;
ans += (i - 2);
ans -= (dp[i - 3][sum[i]]);
}
}
return ans;
}
int main () {
char str[] = "7675636788";
int len = strlen (str);
cout << count (str, len) << endl;
return 0;
} Đầu ra
4
Kết luận
Trong bài toán này, chúng ta đã học cách tìm số chuỗi con chia hết cho 8 và không chia hết cho 3 cùng với mã c ++. Mã này cũng có thể được viết bằng java, python và các ngôn ngữ khác. Để giải quyết vấn đề này, chúng tôi đã đảo ngược một chuỗi để tìm số chuỗi con chia hết cho 8 nhưng không chia hết cho 3. Đây là một vấn đề rất đơn giản khi chúng tôi chia nó thành 2 phần.