คุณจะได้รับตัวเลขเป็นสตริง คุณต้องค้นหาว่าต้องลบตัวเลขกี่หลักจึงจะหารด้วย 3 ลงตัว
เราทำให้ตัวเลขหารลงตัวด้วยการเอาออกไม่เกิน 2 หลัก ดังนั้น จำนวนหลักสูงสุดที่จะลบออกเพื่อให้หารด้วย 3 ลงตัวคือ 2
มาดูตัวอย่างกัน
ป้อนข้อมูล
92
ผลผลิต
1
เราสามารถลบ 2 เพื่อให้หารด้วย 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
