এই সমস্যায়, আমাদেরকে একটি বাইনারি অ্যারে বিন [] দেওয়া হয়েছে যার মধ্যে n বাইনারি মান রয়েছে যা 0 এবং 1 হতে পারে। আমাদের কাজ হল একটি অ্যারেকে সুন্দর করার জন্য প্রয়োজনীয় ন্যূনতম অপারেশনগুলি খুঁজে বের করা।
সুন্দর অ্যারে হল একটি বিশেষ ধরনের বাইনারি অ্যারে যা বিকল্প 0 এবং 1 এর প্যাটার্ন নিয়ে গঠিত।
সমস্যা বর্ণনা − অ্যারেটিকে সুন্দর করার জন্য আমাদের নম্বর অপারেশনগুলি খুঁজে বের করতে হবে। একটি অপারেশন এই ধাপগুলি নিয়ে গঠিত -
ধাপ 1 − অ্যারেটিকে দুই ভাগে কাটুন।
ধাপ 2 − দুটি অর্ধের যেকোনো একটিকে বিপরীত করুন।
ধাপ 3 - যোগদান করুন তারপর অর্ধেক পিছিয়ে দিন।
অ্যারেটি একটি সুন্দর অ্যারেতে পরিণত হয় তা নিশ্চিত করার জন্য প্রয়োজনীয় ক্রিয়াকলাপগুলির সংখ্যা আমরা গণনা করব৷
সমস্যাটি বোঝার জন্য একটি উদাহরণ নেওয়া যাক,
ইনপুট
bin[] = {1, 0, 1, 0, 0, 1} আউটপুট
1
ব্যাখ্যা
আমরা অ্যারেটি কেটে ফেলব, একটি সাবারে বিন তৈরি করব [4, 5], এটিকে বিপরীত করব এবং এটিকে আবার যুক্ত করব।
সমাধান পদ্ধতি
সমস্যার সমাধান হল সুইচ অপারেশনের ন্যূনতম সংখ্যা খোঁজার উপর ভিত্তি করে যা ধারাবাহিক শূন্যের সংখ্যার সমান। বেস কেস হল −
অ্যারের আকার 1 হলে, এটি একটি সুন্দর অ্যারে। যদি অ্যারের আকার একটি বিজোড় সংখ্যা হয় তবে এটি কখনই একটি সুন্দর অ্যারে হতে পারে না৷
৷সমস্ত জোড় দৈর্ঘ্যের জন্য, আমরা ক্রমাগত শূন্য অরোনের মোট সংখ্যা পরীক্ষা করব যা সম্পাদিত অপারেশনের সংখ্যা হবে।
অ্যালগরিদম
শুরু করুন − zeroCount , oneCount, consZero =0
ধাপ 1 − যদি ( n =1), ফেরত 0
ধাপ 2 − যদি (n%2 !=0), রিটার্ন -1।
ধাপ 3 − i -> 0 থেকে n-1 এর জন্য লুপ।
ধাপ ৩.১ − if bin[i] ==bin[i+1] ==0, consZero++।
পদক্ষেপ 4৷ − if bin[n-1] ==bin[0] ==0, consZero++।
ধাপ 5 - কনসজিরো ফেরত দিন।
আমাদের সমাধানের কাজ চিত্রিত করার জন্য প্রোগ্রাম,
উদাহরণ
#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
