এই সমস্যাতে, আমাদের (2n+1) সংখ্যক ইন্টিজার উপাদান বিশিষ্ট একটি অ্যারে দেওয়া আছে। এই সব মানের মধ্য nটি উপাদান দুবার উপস্থিত আছে এবং শুধু একটি উপাদান একবার উপস্থিত আছে। আমাদের কাজ হলো (2n+1) আকারের অ্যারেতে একক উপাদান বের করা।
উদাহরণ দিয়ে সমস্যা বোঝা যাক,
ইনপুট
arr[] = {1, 3, 5, 6, 5, 1, 3}
আউটপুট
6
সমাধানের পদ্ধতি
এই সমস্যার একটি সহজ সমাধান হলো উপাদানগুলোর কাউন্টার (counter) ব্যবহার করা। যদি কোনো উপাদান পাওয়া যায়, তার মান এবং ঘটনার সংখ্যা সংরক্ষণ করা। তারপর টেবিলে যেটির ঘটনার সংখ্যা ১ সেটি খুঁজে বের করা।
একটি দক্ষ সমাধান হবে XOR অপারেশন ব্যবহার করা। এখানে, আমরা অ্যারের সব উপাদানের XOR করব। এই XOR দুবার উপস্থিত উপাদানগুলোর মান ০ করে দিবে। এবং শুধু সেই উপাদানের মান থাকবে যার ঘটনা ১বার।
এটি 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
