এই সমস্যাতে, আমাদের একটি নম্বরের অ্যারে দেওয়া আছে এবং আমাদের সেগুলো নির্দিষ্টভাবে সাজিয়ে সবচেয়ে বড় ভ্যালু বের করতে হবে। শর্ত হলো, ইভেন নম্বর এবং অড নম্বর অর্ডার একই থাকবে অর্থাৎ সব ইভেন নম্বর অর্ডার পরিবর্তন করা যাবে না।
উদাহরণ দিয়ে বুঝি:
ইনপুট: {17, 80, 99, 27, 14, 22}
আউটপুট: 801799271422
ব্যাখ্যা: ইভেন ও অড নম্বরের অর্ডার:
ইভেন: 80 14 22
অড: 17 99 27
এখানে ৯৯ সবচেয়ে বড় নম্বর কিন্তু অড নম্বর অর্ডারে ১৭ এর পরে আসে তাই আমরা ৮০ আগে নিলাম এবং তারপর সিকোয়েনশিয়ালি অরেঞ্জমেন্ট করলাম: 80 17 99 27 14 22
যেহেতু আমরা সমস্যাটি বুঝতে পেরেছি, সমাধান বানাতে চাই। এখানে ক্লাসিক্যাল ডিসেন্ডিং অর্ডার যেতে পারব না কারণ ইভেন ও অড সিকোয়েন্স সম্পর্কে কনস্ট্রেইন্ট আছে। তাই এই সিকোয়েন্স মেইনটেইন করে ইভেন ও অড অর্ডারের ফার্স্ট এলিমেন্টগুলো থেকে যেটি বড় সেটি বেছে নিতে হবে। চলুন একটি অ্যালগরিদম দেখি যা বিষয়টি পরিষ্কার করবে।
অ্যালগরিদম
ধাপ ১: দুটি স্ট্রাকচার বানান, একটি ইভেন অন্যটি অডের জন্য, এতে সিকোয়েন্স মেইনটেইন হবে। ধাপ ২: প্রতিটি স্ট্রাকচার থেকে একটা এলিমেন্ট নিয়ে চেক করুন কোন কম্বিনেশন বড় নম্বর বানায়। উদাহরণ, E হলে ইভেন নম্বর এবং O হলে অড নম্বর যেগুলো স্ট্রাকচার-এর টপে আছে। তবে চেক করুন EO এবং OE-র মধ্যে কোনটি গ্রেটার। ধাপ ৩: গ্রেটার কম্বিনেশন ফাইনাল সিকোয়েন্সে রাখুন। ধাপ ৪: ফাইনাল সিকোয়েন্স প্রিন্ট করুন।
উদাহরণ
এখন, এই অ্যালগরিদম অনুযায়ী প্রোগ্রাম বানাই।
#include <bits/stdc++.h>
using namespace std;
string merge(vector<string> arr1, vector<string> arr2) {
int n1 = arr1.size();
int n2 = arr2.size();
int i = 0, j = 0;
string big = "";
while (i < n1 && j < n2) {
if ((arr1[i] + arr2[j]).compare((arr2[j] + arr1[i])) > 0)
big += arr1[i++];
else
big += arr2[j++];
}
while (i < n1)
big += arr1[i++];
while (j < n2)
big += arr2[j++];
return big;
}
string largestNumber(vector<string> arr, int n) {
vector<string> even, odd;
for (int i = 0; i < n; i++) {
int lastDigit = arr[i].at(arr[i].size() - 1) - '0';
if (lastDigit % 2 == 0)
even.push_back(arr[i]);
else
odd.push_back(arr[i]);
}
string biggest = merge(even, odd);
return biggest;
}
int main() {
vector<string> arr;
arr.push_back("17");
arr.push_back("80");
arr.push_back("99");
arr.push_back("27");
arr.push_back("14");
arr.push_back("22");
int n = arr.size();
cout << "Biggest possible number from the array is = " << largestNumber(arr, n);
return 0;
}
আউটপুট
Biggest possible number from the array is = 801799271422
