โจทย์
คุณได้รับตัวเลขในรูปแบบสตริง คุณต้องหาว่าต้องลบหลักกี่หลักเพื่อให้มันหาร 3 ลงตัว
เราสามารถทำให้เลขหาร 3 ลงตัวได้โดยการลบได้สูงสุด 2 หลัก ดังนั้นจำนวนหลักสูงสุดที่ต้องลบคือ 2
มาดูตัวอย่างกัน
อินพุต
92
เอาต์พุต
1
เราสามารถลบ 2 เพื่อให้ได้ 9 ซึ่งหาร 3 ลงตัว
อินพุต
999
เอาต์พุต
0
เลขที่กำหนดให้มาหาร 3 ลงตัวอยู่แล้ว
อัลกอริธึม
- กำหนดตัวเลขในรูปสตริง
- หาผลรวมของหลักต่างๆ
- ถ้าผลรวมหาร 3 ลงตัว ให้คืนค่า 0
- ถ้าผลรวมไม่หาร 3 ลงตัวและความยาวของเลขเป็น 1 เราไม่สามารถทำให้หาร 3 ลงตัวได้ คืนค่า -1
- วนลูปตรวจสอบแต่ละหลัก
- ลบหลักนั้นออกและตรวจสอบการหารลงตัว
- ถ้าเงื่อนไขเป็นจริง ให้คืนค่า 1
- ตรวจสอบความยาวอีกครั้ง ถ้าความยาวเป็น 2 ให้คืนค่า -1
- มิฉะนั้นคืนค่า 2
การนำไปใช้งาน
ต่อไปนี้เป็นการนำไปใช้งานของอัลกอริธึมข้างต้นใน C++
#include <bits/stdc++.h>
using namespace std;
int getNumSum(string n) {
int len = n.length(), sum = 0;
for (int i = 0; i < len; i++) {
sum += (int)n[i];
}
return sum;
}
int getDigitsCount(string num) {
int n = num.length();
int sum = getNumSum(num);
if (sum % 3 == 0) {
return 0;
}
if (n == 1) {
return -1;
}
for (int i = 0; i < n; i++) {
int currentDigit = num[i] - '0';
if (sum % 3 == currentDigit % 3) {
return 1;
}
}
if (n == 2) {
return -1;
}
return 2;
}
int main() {
string num = "7536836";
cout << getDigitsCount(num) << endl;
return 0;
}
ผลลัพธ์
หากคุณรันโค้ดข้างต้น คุณจะได้ผลลัพธ์ดังนี้
1
