เติม 1 ให้เต็มอาร์เรย์ด้วยจำนวนรอบน้อยที่สุดใน C++

โจทย์

ได้รับอาร์เรย์ arr[] ที่มีแค่ 0 และ 1 ทางเราต้อง หาจำนวนรอบน้อยที่สุดในการเติม 1 ให้เต็มอาร์เรย์ โดยที่ 1 สามารถเปลี่ยนเพื่อนบ้านซ้ายและขวาเป็น 1 ได้ในหนึ่งรอบ

ตัวอย่าง

Input: arr[] = {0, 1, 1, 0, 0, 1}

Output: 1

แนวทางแก้ปัญหา

วิเคราะห์เป็นบล็อก (Blocks) ที่แบ่งด้วย 1:

• Case 1: บล็อก 0 ระหว่าง 1 สองข้าง -> รอบ = ceil(จำนวน 0 / 2)
• Case 2: บล็อก 0 อยู่ปลาย (มี 1 ข้างเดียว) -> รอบ = จำนวน 0
• Case 3: ไม่มี 1 เลย -> ไม่สามารถเติมได้ (return -1)

คำตอบคือค่าสูงสุดของรอบในทุกบล็อก

โปรแกรมตัวอย่าง

#include <iostream>
using namespace std;

int countIterationFill1(int arr[], int n) {
    bool oneFound = false;
    int iterationCount = 0;
    for (int i = 0; i < n; ) {
        if (arr[i] == 1) oneFound = true;
        while (i < n && arr[i] == 1) i++;
        int zeroCount = 0;
        while (i < n && arr[i] == 0) { zeroCount++; i++; }
        if (!oneFound && i == n) return -1;
        int itrCount;
        if (i < n && oneFound) {
            itrCount = (zeroCount + 1) / 2; // ceil(zeroCount/2)
        } else {
            itrCount = zeroCount;
        }
        iterationCount = max(iterationCount, itrCount);
    }
    return iterationCount;
}

int main() {
    int arr[] = {0, 1, 1, 0, 0, 1, 0, 0, 0, 1};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "The number of iterations to fill 1's is " << countIterationFill1(arr, n);
    return 0;
}

ผลลัพธ์

The number of iterations to fill 1's is 2