ในปัญหานี้ เราได้รับ Binary Array bin[] ซึ่งประกอบด้วย n ค่าไบนารีซึ่งมีค่าเท่ากับ 0 และ 1 หน้าที่ของเราคือค้นหาการดำเนินการขั้นต่ำที่จำเป็นในการทำให้ Array สวยงาม
อาร์เรย์ที่สวยงามเป็นอาร์เรย์ไบนารีชนิดพิเศษซึ่งประกอบด้วยรูปแบบของ 0 และ 1 สำรอง
คำอธิบายปัญหา − เราจำเป็นต้องค้นหาการดำเนินการของตัวเลขที่จำเป็นในการทำให้อาร์เรย์สวยงาม การดำเนินการประกอบด้วยขั้นตอนเหล่านี้ -
ขั้นตอนที่ 1 − ตัดอาร์เรย์ออกเป็นสองส่วน
ขั้นตอนที่ 2 − กลับด้านใดด้านหนึ่งของทั้งสองส่วน
ขั้นตอนที่ 3 − เข้าร่วมแล้วแบ่งครึ่งกลับ
เราจะนับจำนวนการดำเนินการที่จำเป็นเพื่อให้แน่ใจว่าอาร์เรย์จะกลายเป็นอาร์เรย์ที่สวยงาม
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน
อินพุต
bin[] = {1, 0, 1, 0, 0, 1} ผลลัพธ์
1
คำอธิบาย
เราจะตัดอาร์เรย์ สร้าง subarray bin[4, 5] ย้อนกลับและรวมกลับ
แนวทางการแก้ปัญหา
วิธีแก้ปัญหาขึ้นอยู่กับการหาจำนวนขั้นต่ำของการทำงานของสวิตช์ซึ่งเท่ากับจำนวนศูนย์ที่ต่อเนื่องกัน กรณีพื้นฐานคือ −
ถ้าขนาดของอาร์เรย์เท่ากับ 1 แสดงว่าอาร์เรย์ที่สวยงาม หากขนาดของอาร์เรย์เป็นจำนวนคี่ อาร์เรย์นั้นจะไม่สามารถเป็นอาร์เรย์ที่สวยงามได้
สำหรับความยาวที่เท่ากันทั้งหมด เราจะตรวจสอบจำนวนรวมของศูนย์หรือศูนย์ที่ต่อเนื่องกันซึ่งจะเป็นจำนวนการดำเนินการที่จะดำเนินการ
อัลกอริทึม
Initialise − zeroCount , oneCount, consZero =0
ขั้นตอนที่ 1 − ถ้า ( n =1) ให้คืนค่า 0
ขั้นตอนที่ 2 − ถ้า (n%2 !=0) ให้คืนค่า -1
ขั้นตอนที่ 3 − วนรอบสำหรับ i -> 0 ถึง n-1
ขั้นตอนที่ 3.1 − ถ้า bin[i] ==bin[i+1] ==0, consZero++.
ขั้นตอนที่ 4 − if bin[n-1] ==bin[0] ==0, consZero++.
ขั้นตอนที่ 5 − คืนค่า consZero
โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา
ตัวอย่าง
#include <iostream>
using namespace std;
int minOperations(int bin[], int n) {
if(n == 1)
return 0;
if(n%2 != 0)
return -1;
int consZero = 0;
for (int i = 0; i < n; ++i) {
if (i + 1 < n) {
if (bin[i] == 0 && bin[i + 1] == 0)
consZero++;
}
}
if (bin[0] == bin[n - 1] && bin[0] == 0)
consZero++;
return consZero;
}
int main() {
int bin[] = { 1, 0, 1, 0, 0, 1};
int n = sizeof(bin) / sizeof(bin[0]);
cout<<"The minimum operations needed to make an Array beautiful is "<<minOperations(bin, n);
return 0;
} ผลลัพธ์
The minimum operations needed to make an Array beautiful is 1
