আমাদের একটি বাইনারি অ্যারে দেওয়া আছে যেটি যেকোনো দেওয়া আকারে ১ এবং ০ ডিজিট সংরক্ষণ করতে পারে এবং একটি পূর্ণসংখ্যা ভেরিয়েবল ধরুন, base। কাজটি হল সেই বাইনারি অ্যারেতে ন্যূনতম ১-এঁ গণনা করা যারা অ্যারের অন্যান্য উপাদানকে পাওয়ার লেন্ড করতে পারবে যাতে পুরো অ্যারে পাওয়ারফুল হয়। একটি উপাদান তার আডজেসেন্ট উপাদানকে বা base-এর চেয়ে কম দূরত্বে যেকোনো উপাদানকে পাওয়ার লেন্ড করতে পারে।
বিভিন্ন ইনপুট-আউটপুট পরিস্থিতি দেখে নিই -
ইন - int arr[] = {1, 1, 0, 1, 1, 0, 1}, int base = 7
আউট - পুরো অ্যারেকে পাওয়ারফুল बनाने জন্য ন্যূনতম ১-এঁ লেন্ড পাওয়ার: 1
ব্যাখ্যা - আমাদের আকার ৭-এর একটি বাইনারি অ্যারে দেওয়া আছে এবং base-এর মান ৭ অর্থাৎ প্রথম অঙ্ক ১ পুরো অ্যারেকে পাওয়ার লেন্ড করতে পারে। তাই arr[1]-এ থাকা ১ অন্য সকল উপাদানকে পাওয়ার লেন্ড করতে পারে।
ইন - int arr[] = {1, 1, 0, 1, 1, 0, 1}, int base = 3
আউট - পুরো অ্যারেকে পাওয়ারফুল बनाने জন্য ন্যূনতম ১-এঁ লেন্ড পাওয়ার: 2
ব্যাখ্যা - আমাদের আকার ৭-এর একটি বাইনারি অ্যারে দেওয়া আছে এবং base-এর মান ২ অর্থাৎ প্রথম ১ পরবর্তী দুটি উপাদানকে পাওয়ার লেন্ড করতে পারে। তাই arr[2]-এ থাকা ১ পরবর্তী দুটি উপাদানকে পাওয়ার লেন্ড করতে পারে এবং arr[5]-এ থাকা অন্য একটি ১ পরবর্তী দুটি উপাদানকে পাওয়ার লেন্ড করতে পারে যা পুরো অ্যারেকে পাওয়ারফুল করে।
ইন - int arr[] = {1, 1, 0, 1, 1, 0, 1}, int base = 1
আউট - পুরো অ্যারেকে পাওয়ারফুল बनाना অসম্ভব
ব্যাখ্যা - আমাদের আকার ৭-এর একটি বাইনারি অ্যারে দেওয়া আছে এবং base-এর মান ১ অর্থাৎ প্রথম ১ শুধু পরবর্তী একক উপাদানকে পাওয়ার লেন্ড করতে পারে। তাই পুরো অ্যারেকে পাওয়ারফুল बनाना অসম্ভব।
নিচের প্রোগ্রামে ব্যবহৃত পদ্ধতি -
- যেকোনো দেওয়া আকারের একটি বাইনারি অ্যারে এবং একটি পূর্ণসংখ্যা ভেরিয়েবল base ইনপুট নিন।
- অ্যারের আকার গণনা করুন এবং val নামে একটি পূর্ণসংখ্যা টাইপের ভেরিয়েবল ডিক্লেয়ার করুন।
- val-কে একটি ফাংশন কল দিয়ে সেট করুন যা ন্যূনতম ১-এঁ রিটার্ন করবে একটি পাওয়ারফুল অ্যারে তৈরি করতে এবং যদি সম্ভব না হয় তবে -1 রিটার্ন করবে যা পরে এরর মেসেজ দেখাবে।
- Lend_Power(int arr[], int size, int base) ফাংশনের ভিতরে:
- বাইনারি অ্যারের আকারের সাথে একটি পূর্ণসংখ্যা টাইপের মান 지닌 অ্যারে ডিক্লেয়ার করুন।
- temp = -1 এবং count = 0 নামে টেম্পরারি ভেরিয়েবল ডিক্লেয়ার করুন।
- i = ০ থেকে অ্যারের আকার পর্যন্ত একটি FOR লুপ শুরু করুন। লুপের ভিতরে, চেক করুন IF arr[i] == 1 তবে temp = i এবং arr_2[i] = temp সেট করুন।
- ০ থেকে অ্যারের আকার পর্যন্ত একটি FOR লুপ শুরু করুন এবং reset_base = i + base - 1 এবং reset_size = size - 1 সেট করুন। set = arr_2[min(reset_base, reset_size)] ভেরিয়েবল সেট করুন।
- চেক করুন IF set == -1 OR set + base <= i তবে -1 রিটার্ন করুন।
- ভেরিয়েবল 'i' = set + base সেট করুন।
- count রিটার্ন করুন।
উদাহরণ
#include<bits/stdc++.h>
using namespace std;
int Lend_Power(int arr[], int size, int base) {
int arr_2[size];
int temp = -1;
int count = 0;
for(int i = 0; i < size; i++)
{
if(arr[i] == 1)
{
temp = i;
}
arr_2[i] = temp;
}
for(int i = 0; i < size;)
{
int reset_base = i + base - 1;
int reset_size = size - 1;
int set = arr_2[min(reset_base, reset_size)];
if(set == -1 || set + base <= i)
{
return -1;
}
i = set + base;
count++;
}
return count;
}
int main() {
int arr[] = {1, 1, 0, 1, 1, 0, 1};
int base = 2;
int size = sizeof(arr) / sizeof(arr[0]);
int val = Lend_Power(arr, size, base);
if(val == -1)
{
cout<<"Impossible to make entire array powerful";
}
else
{
cout<<"Minimum 1s to lend power to make whole array powerful are: "<<val;
}
return 0;
}
আউটপুট
উপরোক্ত কোডটি রান করলে নিচের আউটপুটটি জেনারেট হবে
Minimum 1s to lend power to make whole array powerful are: 3
