การตัดตัวเลขที่เป็นไปได้ เพื่อให้ส่วนส่วนมากหาร 3 ลงตัวใน C++

ในปัญหานี้ เราได้รับค่าจำนวนเต็มขนาดใหญ่ (สูงสุด 10⁵ หลัก) งานของเราคือพิมพ์จำนวนการตัดทั้งหมดที่จำเป็น เพื่อให้ส่วนส่วนมากหาร 3 ลงตัว

มาดูตัวอย่างเพื่อเข้าใจปัญหา:

Input - 9216

Output - 3

Explanation - ตัวเลขถูกแบ่งเป็น 9|21|6

เพื่อแก้ปัญหานี้ เราจะต้องเริ่มจาก least significant bit ของตัวเลข คือ หลักสุดท้ายของตัวเลข ที่นี่ เราจะหาตัวเลขที่เล็กที่สุดที่หาร 3 ลงตัว และอัปเดตจำนวนตามนั้น

ตัวอย่าง - หาก arr[i] ทำให้ได้ตัวเลขที่หาร 3 ลงตัว เราจะเพิ่มจำนวนและไปยังหลักถัดไปของตัวเลข หาก arr[i] ไม่หาร 3 ลงตัว เราจะรวมกับหลักถัดไปและตรวจสอบการหาร 3 ลงตัว

Divisibility of 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