এই সমস্যায়, আমাদেরকে (2n+ 1) পূর্ণসংখ্যার মান সমন্বিত একটি অ্যারে দেওয়া হয়েছে৷ এই সমস্ত মানের মধ্যে, n উপাদানগুলি অ্যারেতে দুবার উপস্থিত হয় এবং অ্যারেতে শুধুমাত্র একটি উপাদান রয়েছে৷ যে একবার প্রদর্শিত হয়. আমাদের কাজ হল 2n+1 পূর্ণসংখ্যা উপাদানগুলির অ্যানারেতে একক খুঁজে বের করা৷
সমস্যাটি বোঝার জন্য একটি উদাহরণ নেওয়া যাক,
ইনপুট
arr[] = {1, 3, 5, 6, 5, 1, 3} আউটপুট
5
সমাধান পদ্ধতি
সমস্যার একটি সহজ সমাধান হল উপাদানগুলির জন্য একটি কাউন্টার ব্যবহার করা। যদি একটি উপাদান সম্মুখীন হয়, তার মান এবং সংঘটন গণনা সংরক্ষণ করুন. এই অনুসন্ধানের পরে টেবিলে উপাদানটির জন্য যার সংঘটন সংখ্যা =1। আরও একটি দক্ষ সমাধান XOR ব্যবহার করা হবে। এখানে, আমরা অ্যারের সমস্ত উপাদানের XOR সম্পাদন করব। এই XOR সমস্ত উপাদানকে দ্বিগুণ সংঘটন 0 তৈরি করবে। এবং একমাত্র উপাদান যার মান উপস্থিত থাকবে সেটি হল যার উপস্থিতি 1।
এটি XOR এর বৈশিষ্ট্যগুলির কারণে যা হল −
- a^a = 0 - a^0 = a
আমাদের সমাধানের কাজ চিত্রিত করার জন্য প্রোগ্রাম,
উদাহরণ
#include <iostream>
using namespace std;
int findSingleValue(int arr[], int n) {
int element = 0;
for (int i = 0; i < n; i++)
element = element ^ arr[i];
return element;
}
int main() {
int arr[] = { 1, 3, 5, 6, 5, 1, 3 };
int n = sizeof(arr) / sizeof(arr[0]);
cout<<"The element of the array with single occurrence is "<<findSingleValue(arr, n);
return 0;
} আউটপুট
The element of the array with single occurrence is 6
