এই সমস্যায়, আমাদেরকে n এবং n+1 আকারের দুটি সাজানো অ্যারে arr1 এবং arr2 দেওয়া হয়েছে অতিরিক্ত উপাদান বাদে সমস্ত উপাদান একই সাথে। আমাদের কাজ হল একটি সাজানো অ্যারেতে উপস্থিত একটি অতিরিক্ত উপাদানের সূচী খুঁজে পাওয়া .
সমস্যা বর্ণনা: আমাদের n+1 আকারের অ্যারে থেকে একটি উপাদানের সূচী খুঁজে বের করতে হবে যা n আকারের অ্যারেতে নেই।
সমস্যাটি বোঝার জন্য একটি উদাহরণ নেওয়া যাক,
ইনপুট: arr1[n] ={3, 5, 7, 8, 9, 12}
arr2[n+1] ={3, 4, 5, 7, 8, 9, 12}
আউটপুট: 1
ব্যাখ্যা:
মান 4 সহ উপাদানটি অতিরিক্ত যা সূচক 1 এ রয়েছে।
সমাধান পদ্ধতি -
সমস্যার একটি সহজ সমাধান হল যে উভয় অ্যারে সাজানো হয় তা ব্যবহার করে। এবং শুধুমাত্র একটি উপাদানের সাথে যা সমান নয়, আমরা রৈখিক অনুসন্ধান করতে পারি এবং arr2 এ উপাদানটি খুঁজে পেতে পারি যেটি arr1[] এ নেই।
অ্যালগরিদম:
ধাপ 1: i -> 0 থেকে n+1,
এর জন্য লুপধাপ 1.1: বিজোড় উপাদান খুঁজুন, যদি arr1[i] !=arr2[i], ব্রেক লুপ।
ধাপ 2: i এর মান ফেরত দিন।
আমাদের সমাধানের কাজ চিত্রিত করার জন্য প্রোগ্রাম,
উদাহরণ
#include <iostream>
using namespace std;
int findExtraElement(int arr1[], int arr2[], int n) {
int i;
for (i = 0; i < n; i++)
if (arr1[i] != arr2[i])
break;
return i;
}
int main()
{
int arr1[] = {3, 5, 7, 8, 9, 12};
int arr2[] = {3, 4, 5, 7, 8, 9, 12};
int n = sizeof(arr1) / sizeof(arr1[0]);
int extraIndex = findExtraElement(arr1, arr2, n);
cout<<"The extra element is at index ("<<extraIndex<<") and the value is "<<arr2[extraIndex];
return 0;
} আউটপুট
The extra element is at index (1) and the value is 4
এই সমাধানটি আরও কার্যকর অনুসন্ধান কৌশল ব্যবহার করে আরও ভাল করা যেতে পারে যা হল বাইনারী অনুসন্ধান লিনিয়ারের পরিবর্তে অ্যালগরিদমের গণনার সময় হ্রাস করুন:
আমাদের সমাধানের কাজ চিত্রিত করার জন্য প্রোগ্রাম,
উদাহরণ
#include <iostream>
using namespace std;
int findExtraElement(int arr1[], int arr2[], int n) {
int extraIndex = n;
int start = 0, end = n - 1;
while (start <= end)
{
int mid = (start + end) / 2;
if (arr2[mid] == arr1[mid])
start = mid + 1;
else
{
extraIndex = mid;
end = mid - 1;
}
}
return extraIndex;
}
int main()
{
int arr1[] = {3, 5, 7, 8, 9, 12};
int arr2[] = {3, 4, 5, 7, 8, 9, 12};
int n = sizeof(arr1) / sizeof(arr1[0]);
int extraIndex = findExtraElement(arr1, arr2, n);
cout<<"The extra element is at index ("<<extraIndex<<") and the value is "<<arr2[extraIndex];
return 0;
} আউটপুট
The extra element is at index (1) and the value is 4
আরেকটি পদ্ধতি:
সমস্যা সমাধানের আরও একটি পদ্ধতি হল দুটি অ্যারের মধ্যে পরম পার্থক্য খুঁজে বের করা, যা অতিরিক্ত উপাদান। তারপরে আমাদের n+1 আকারের অ্যারেতে এই অতিরিক্ত উপাদানটির সূচক খুঁজে বের করতে হবে। এটি একটি অনুসন্ধান অ্যালগরিদম ব্যবহার করে করা যেতে পারে৷
৷আমাদের সমাধানের কাজ চিত্রিত করার জন্য প্রোগ্রাম,
উদাহরণ
#include <iostream>
using namespace std;
int calcArraysum(int arr[], int n){
int sum = 0;
for(int i = 0; i < n; i++)
sum += arr[i];
return sum;
}
int findExtraElement(int arr1[], int arr2[], int n) {
int extraValue = calcArraysum(arr2, n+1) - calcArraysum(arr1, n);
for (int i = 0; i < n; i++)
{
if (arr2[i] == extraValue)
return i;
}
return -1;
}
int main()
{
int arr1[] = {3, 5, 7, 8, 9, 12};
int arr2[] = {3, 4, 5, 7, 8, 9, 12};
int n = sizeof(arr1) / sizeof(arr1[0]);
int extraIndex = findExtraElement(arr1, arr2, n);
cout<<"The extra element is at index ("<<extraIndex<<") and the value is "<<arr2[extraIndex];
return 0;
} আউটপুট
The extra element is at index (1) and the value is 4
