Trong bài toán này, chúng ta được cho một số và chúng ta phải xóa thêm chữ số khỏi số. Sao cho số mới tạo thành sau khi loại bỏ chia hết cho 6.
Hãy lấy một ví dụ để tìm hiểu khái niệm tốt hơn -
Input : 1324 Output : 4
Giải thích - Bỏ số thứ 4 ta được 132 chia hết cho 6.
Ở đây, chúng ta được cho một số và chúng ta phải trả lại vị trí mà từ đó số bị xóa để chia hết cho 6.
Để giải quyết vấn đề này, chúng tôi sẽ cố gắng tạo ra một logic để giải quyết vấn đề. Để làm được điều này, chúng ta sẽ sử dụng kiến thức của mình rằng nếu một số chia hết cho 2 và 3 thì nó chia hết cho 6.
Sau khi xóa chữ số khỏi số, số mới được tạo thành sẽ được kiểm tra tính chia hết cho 6, tức là chia hết cho 2 và 3.
Phương pháp tiếp cận
Dựa vào số ta có thể tìm xem số được tạo ra bằng cách xóa đi một chữ số sẽ chia hết cho 6 hay không. Có hai điều kiện phát sinh nếu chúng ta nhìn thấy chữ số cuối cùng của số.
Khi chữ số cuối cùng là số lẻ
Khi chữ số cuối cùng là số lẻ, cách duy nhất có thể là loại bỏ chữ số cuối cùng. Và số mới sẽ không chia hết cho 6 chỉ khi chữ số bên cạnh chữ số cuối cùng là số chẵn. Nếu không, giải pháp là không thể.
Khi chữ số cuối cùng là chẵn
Nếu chữ số cuối cùng là chẵn thì chúng ta phải tìm phần dư khi số đó chia hết cho 3. và dựa vào số này, chúng ta có thể kiểm tra xem có thể loại bỏ chữ số nào.
Chia số cho 3 ba trường hợp -
Phần còn lại là 1 - Nếu phần dư của phép chia là 1 thì có thể xóa bất kỳ chữ số 1, 4, 7 nào khỏi mảng. Nếu có nhiều chữ số để xóa thì chúng tôi sẽ xóa chữ số theo cách sao cho số được hình thành sau khi xóa là số lớn nhất.
Phần còn lại là 2 - Nếu số dư của phép chia là 2 thì có thể xóa bất kỳ chữ số 2, 5, 8 nào khỏi mảng. Nếu có nhiều chữ số để xóa thì chúng tôi sẽ xóa chữ số theo cách sao cho số được hình thành sau khi xóa là số lớn nhất.
Phần còn lại là 3 - Nếu phần dư của phép chia là 1 thì có thể xóa bất kỳ chữ số 3, 6, 9 nào khỏi mảng. Nếu có nhiều chữ số để xóa thì chúng tôi sẽ xóa chữ số theo cách sao cho số được hình thành sau khi xóa là số lớn nhất.
Dựa trên những điều này, hãy giải quyết một số vấn đề và tìm ra kết quả mong muốn -
Khi chữ số cuối cùng là số lẻ
1. 34241341
Trong trường hợp này, chữ số duy nhất có thể bị xóa là 1 ở vị trí cuối cùng và số được tạo thành sẽ là 3432134 chia hết cho 6. Vì vậy, chúng tôi sẽ trả lại vị trí của 1 đã bị loại bỏ, tức là 8
2. 3214241
Trong trường hợp này, chữ số duy nhất có thể bị xóa là 1 ở vị trí cuối cùng và số được tạo thành sẽ là 341224. Không chia hết cho 6. Vì vậy, chúng ta sẽ trả về -1.
Khi chữ số cuối cùng là chẵn
1. 8097860
Trong trường hợp này, chúng ta cần chia số cho 3 và tìm số dư bằng 2. Vì vậy, trong trường hợp 2 là số dư, chúng ta có thể loại bỏ 2, 5, 8 khỏi số. Vì vậy, 8 từ vị trí 1 và 5 có thể được loại bỏ để làm cho số chia hết cho 2. Chúng ta sẽ loại bỏ 8 ở vị trí thứ 5 vì nếu chúng ta loại bỏ nó từ vị trí đầu tiên thì số nhỏ hơn sẽ được trả lại. Số mới được hình thành sẽ là 809760 chia hết cho 6. Vì vậy, chúng ta sẽ trả về 5.
Ví dụ
Dựa trên logic này, hãy tạo một chương trình để giải quyết vấn đề -
#include <bits/stdc++.h>
using namespace std;
void isDivisibleBy6(string num){
int n = num.length();
int a[n];
int sum = 0;
for (int i = 0; i < n; i++) {
a[i] = num[i] - '0';
sum += a[i];
}
if (a[n - 1] % 2){
if ( (a[n - 2] % 2 != 0) || (sum - a[n - 1]) % 3 != 0) {
cout << "-1" << endl;
}
else {
cout << n << endl;
}
}
else {
int re = sum % 3;
int del = -1;
int flag = 0;
for (int i = 0; i < n - 1; i++) {
if ((a[i]) % 3 == re) {
if (a[i + 1] > a[i]) {
del = i;
flag = 1;
break;
}
else {
del = i;
}
}
}
if (flag == 0) {
if (a[n - 2] % 2 == 0 and re == a[n - 1] % 3)
del = n - 1;
}
if (del == -1)
cout << -1 << endl;
else {
cout << del + 1 << endl;
}
}
}
int main(){
string number = "343224152";
isDivisibleBy6(number);
return 0;
} Đầu ra
5