ในปัญหานี้ เราได้รับค่าจำนวนเต็มจำนวนมาก (สูงสุด 10 5 ตัวเลข) งานของเราคือพิมพ์จำนวนการตัดทั้งหมดที่ต้องการ โดยให้ส่วนสูงสุดหารด้วย 3 ลงตัว
มาดูตัวอย่างทำความเข้าใจปัญหากัน
ป้อนข้อมูล − 9216
ผลลัพธ์ − 3
คำอธิบาย − จำนวนหารด้วย 9|21|6.
ในการแก้ปัญหานี้ เราจะต้องเริ่มด้วยบิตที่มีนัยสำคัญน้อยที่สุด นั่นคือ หลักสุดท้ายของตัวเลข สำหรับตรงนี้ เราจะหาจำนวนที่น้อยที่สุดที่หารด้วยสามได้ แล้วอัปเดตจำนวนตามนั้น
ตัวอย่าง − ถ้า arr[i] สร้างตัวเลขที่แบ่งได้ 3 ตัว เราจะเพิ่มจำนวนและย้ายไปยังหลักถัดไปของตัวเลข หาก arr[i] ไม่หารด้วย 3 ลงตัว เราจะรวมมันกับหลักถัดไปและตรวจสอบการหารด้วย 3 ลงตัว
การหารด้วย 3 − ตัวเลขหารด้วย 3 ลงตัวถ้าจำนวนหลักของตัวเลขหารด้วยสามลงตัว
ตัวอย่าง
โปรแกรมแสดงการใช้งานโซลูชันของเรา
#include <bits/stdc++.h>
using namespace std;
int countMaximum3DivisibleNumbers(string number){
int n = number.length();
vector<int> remIndex(3, -1);
remIndex[0] = 0;
vector<int> counter(n + 1);
int r = 0;
for (int i = 1; i <= n; i++) {
r = (r + number[i-1] - '0') % 3;
counter[i] = counter[i-1];
if (remIndex[r] != -1)
counter[i] = max(counter[i], counter[remIndex[r]] + 1);
remIndex[r] = i+1;
}
return counter[n];
}
int main() {
string number = "216873491";
cout<<"The number of 3 divisible number created by cutting "<<number<<" are : " <<countMaximum3DivisibleNumbers(number);
return 0;
} ผลลัพธ์
The number of 3 divisible number created by cutting 216873491 are : 5
