Điền vào mảng bằng số 1 bằng cách sử dụng số lần lặp lại tối thiểu để lấp đầy các hàng xóm trong C ++

Trong bài toán này, chúng ta được cung cấp một mảng arr bao gồm n phần tử là 0 hoặc 1. Nhiệm vụ của chúng ta là lấp đầy mảng bằng 1 bằng cách sử dụng số lần lặp lại tối thiểu để lấp đầy các vùng lân cận.

Hãy lấy một ví dụ để hiểu vấn đề,

Đầu vào: arr [] ={0, 1, 1, 0, 0, 1}

Đầu ra: 1

Phương pháp tiếp cận Giải pháp -

Để giải quyết vấn đề, chúng ta cần biết thực tế rằng nếu 1 có mặt ở một vị trí, nó có thể chuyển đổi hai số 0 lân cận thành 1.

Nếu, arr [i] là 1.
Sau đó, arr [i-1] và arr [i + 1] sẽ được chuyển đổi thành 1.

Bằng cách sử dụng này, giải pháp có thể được tìm thấy bằng cách sử dụng một trong các trường hợp sau -

Trường hợp 1: Khối có 1 ở đầu và cuối khối. Còn lại tất cả các giá trị là 0. Đếm số lượng số không.

Số lần lặp =zeroCount / 2 nếu số là chẵn

Số lần lặp =(zeroCount -1) / 2 nếu số lượng là lẻ

Trường hợp 2: Khối có 1 duy nhất ở đầu hoặc cuối khối và tất cả các giá trị còn lại đều bằng 0.

Số lần lặp =zeroCount

Trường hợp 3: Khối không có số 1. In -1 biểu thị việc điền 1 là không thể.

Chương trình minh họa hoạt động của giải pháp của chúng tôi,

Ví dụ

#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 == false && i == n)
         return -1;
      int itrCount;
      if (i < n && oneFound == true) {
         
         if (zeroCount & 1 == 0)
            itrCount = zeroCount/2;
         else
            itrCount = (zeroCount+1)/2;
         zeroCount = 0;
      }
      else{
         
         itrCount = zeroCount;
         zeroCount = 0;
      }
      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;
}

Đầu ra -

The number of iterations to fill 1's is 2