ในปัญหานี้เราได้รับตัวเลขและเราต้องลบตัวเลขเพิ่มเติมออกจากตัวเลข เพื่อให้จำนวนใหม่ที่เกิดขึ้นหลังจากการลบหารด้วย 6 หารด้วย 6
มาดูตัวอย่างเพื่อเรียนรู้แนวคิดกันดีกว่า −
Input : 1324 Output : 4
คำอธิบาย − เมื่อเอาเลข 4 ออก เราจะได้ 132 หารด้วย 6 ลงตัว
ที่นี่เราได้รับตัวเลขและต้องคืนตำแหน่งจากตำแหน่งที่ลบตัวเลขออกเพื่อให้หารด้วย 6 ลงตัว
สำหรับการแก้ปัญหานี้ เราจะพยายามสร้างตรรกะที่แก้ปัญหาได้ สำหรับสิ่งนี้ เราจะใช้ความรู้ที่ว่าถ้าตัวเลขหารด้วย 2 ลงตัว 3 ก็จะหารด้วย 6 ลงตัว
หลังจากลบตัวเลขออกจากตัวเลขแล้ว หมายเลขใหม่ที่สร้างขึ้นจะถูกตรวจสอบการหารของ 6 นั่นคือการหาร 2 และ 3 ทั้งคู่
แนวทาง
จากตัวเลขเราสามารถหาได้ว่าตัวเลขที่สร้างโดยการลบหลักจะหารด้วย 6 หรือไม่ มีสองเงื่อนไขหากเราเห็นหลักสุดท้ายของตัวเลข
เมื่อหลักสุดท้ายเป็นเลขคี่
เมื่อหลักสุดท้ายเป็นเลขคี่ ทางเดียวที่ทำได้คือลบหลักสุดท้าย และเลขใหม่จะไม่หารด้วย 6 ต่อเมื่อหลักถัดจากหลักสุดท้ายเป็นเลขคู่เท่านั้น มิฉะนั้นจะไม่มีทางแก้ไขได้
เมื่อหลักสุดท้ายเป็นเลขคู่
หากหลักสุดท้ายเป็นเลขคู่ เราต้องหาเศษที่เหลือเมื่อหารด้วย 3 และจากตัวเลขนี้ เราจะสามารถตรวจสอบได้ว่าสามารถลบหลักใดได้บ้าง
ในการหารจำนวนด้วย 3 สามกรณี −
เหลือ 1 − หากเศษที่เหลือของการหารเป็น 1 ตัวเลขใดๆ 1, 4, 7 ก็สามารถลบออกจากอาร์เรย์ได้ หากสามารถลบตัวเลขได้หลายหลัก เราจะลบตัวเลขนั้นออกในลักษณะที่ตัวเลขที่เกิดขึ้นหลังจากการลบออกจะมีจำนวนมากที่สุด
เหลือ 2 − หากเศษที่เหลือของการหารเป็น 2 ตัวเลขใดๆ 2, 5, 8 จะถูกลบออกจากอาร์เรย์ หากสามารถลบตัวเลขได้หลายหลัก เราจะลบตัวเลขดังกล่าวออกในลักษณะที่ตัวเลขที่เกิดขึ้นหลังจากการลบออกจะมีจำนวนมากที่สุด
เหลือ 3 − หากเศษที่เหลือของการหารเป็น 1 เลข 3, 6, 9 ใดๆ จะถูกลบออกจากอาร์เรย์ หากสามารถลบตัวเลขได้หลายหลัก เราจะลบตัวเลขดังกล่าวออกในลักษณะที่ตัวเลขที่เกิดขึ้นหลังจากการลบออกจะมีจำนวนมากที่สุด
จากสิ่งเหล่านี้ มาแก้ปัญหาเล็กน้อยและค้นหาผลลัพธ์ที่ต้องการ -
เมื่อหลักสุดท้ายเป็นเลขคี่
1. 34241341
ในกรณีนี้ หลักเดียวที่สามารถลบออกได้คือ 1 จากตำแหน่งสุดท้าย และจำนวนที่เกิดขึ้นจะเป็น 3432134 ซึ่งหารด้วย 6 ลงตัว ดังนั้นเราจะคืนตำแหน่ง 1 ที่ถูกลบ เช่น 8
2. 3214241
ในกรณีนี้ หลักเดียวที่สามารถลบออกได้คือ 1 จากตำแหน่งสุดท้าย และจำนวนที่เกิดขึ้นจะเป็น 341224 ซึ่งหารด้วย 6 ไม่ลงตัว ดังนั้นเราจะคืนค่า -1
เมื่อหลักสุดท้ายเป็นเลขคู่
1. 8097860
ในกรณีนี้ เราต้องหารตัวเลขด้วย 3 แล้วหาเศษเหลือเท่ากับ 2 ดังนั้น ในกรณีของ 2 เป็นเศษที่เหลือ เราสามารถลบ 2, 5, 8 ออกจากตัวเลขได้ ดังนั้น 8 จากตำแหน่งที่ 1 และ 5 สามารถลบออกเพื่อให้จำนวนหารด้วย 2 หารด้วย 2 เราจะลบ 8 ออกจากตำแหน่งที่ 5 เพราะถ้าเราลบออกจากตำแหน่งที่ 1 จำนวนที่น้อยกว่าจะถูกส่งคืน จำนวนใหม่ที่เกิดขึ้นจะเป็น 809760 ซึ่งหารด้วย 6 ลงตัว ดังนั้นเราจะคืนค่า 5.
ตัวอย่าง
ตามตรรกะนี้ ให้สร้างโปรแกรมเพื่อแก้ปัญหา -
#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;
} ผลลัพธ์
5
