কনসেপ্ট
দুটি অ্যারে দেওয়া আছে যারা একে অপরের ডুপ্লিকেট বাদে একটি উপাদানে ভিন্ন। অর্থাৎ একটি অ্যারে থেকে একটা উপাদান অনুপস্থিত। সেই অনুপস্থিত উপাদানটি খুঁজে বের করুন।
ইনপুট ১
arr1[] = {2, 5, 6, 8, 10} arr2[] = {5, 6, 8, 10}
আউটপুট ১
2
২ দ্বিতীয় অ্যারেতে অনুপস্থিত।
ইনপুট ২
arr1[] = {3, 4, 5, 6} arr2[] = {3, 4, 5, 6, 7}
আউটপুট ২
7
৭ প্রথম অ্যারেতে অনুপস্থিত।
পদ্ধতি
সহজ সমাধান: লিনিয়ার টাইমে উপাদান율 মিলিয়ে যাচাই করুন।
দক্ষ সমাধান (বাইনারি সার্চ): বড় অ্যারেতে বাইনারি সার্চ করুন। mid = (low+high)/2। যদি mid-এ উপাদানগুলো সমান হয় তবে missing উপাদান ডানপাশে (low = mid), নয় তবে বামপাশে (high = mid)। বিশেষ কেস: প্রথম উপাদান ভিন্ন হলে সেটিই missing।
উদাহরণ (C++ কোড)
// C++ প্রোগ্রাম: একই অ্যারে থেকে (একটি উপাদান বাদে) অনুপস্থিত উপাদান খুঁজে বের
#include <bits/stdc++.h>
using namespace std;
// বাইনারি সার্চ দিয়ে missing উপাদান খুঁজে বের
int findMissingUtil(int arrA[], int arrB[], int Q) {
if (Q == 1) return arrA[0]; // শুধু এক উপাদান missing
if (arrA[0] != arrB[0]) return arrA[0]; // প্রথম উপাদান missing
int low = 0, high = Q - 1;
while (low < high) {
int mid = (low + high) / 2;
if (arrA[mid] == arrB[mid]) low = mid;
else high = mid;
if (low == high - 1) break;
}
return arrA[high]; // missing উপাদান বড় অ্যারেতে high ইনডেক্সে
}
// বেসিক চেক এবং কল
void findMissing(int arrA[], int arrB[], int P, int Q) {
if (Q == P - 1) cout << "Missing Element is " << findMissingUtil(arrA, arrB, P) << endl;
else if (P == Q - 1) cout << "Missing Element is " << findMissingUtil(arrB, arrA, Q) << endl;
else cout << "Invalid Input";
}
int main() {
int arrA[] = {2, 5, 6, 8, 10};
int arrB[] = {5, 6, 8, 10};
int P = sizeof(arrA) / sizeof(int);
int Q = sizeof(arrB) / sizeof(int);
findMissing(arrA, arrB, P, Q);
return 0;
}
আউটপুট
Missing Element is 2
