এই সমস্যায়, আমরা n পূর্ণসংখ্যা মানের একটি অ্যারের অ্যারে। আমাদের কাজ হল পূর্ণসংখ্যার বিন্যাসে প্রথম পুনরাবৃত্তিকারী উপাদান খুঁজে পাওয়া .
আমাদের অ্যারে থেকে প্রথম পূর্ণসংখ্যার মান খুঁজে বের করতে হবে যা অ্যারেতে একাধিকবার ঘটেছে।
সমস্যাটি বোঝার জন্য একটি উদাহরণ নেওয়া যাক,
Input : arr[] = {4, 1, 8, 9, 7, 2, 1, 6, 4}
Output : 4 ব্যাখ্যা −
Integers with more than one occurrence are 4 and 1. 4's first occurrence is smaller than 1. Hence the answer is 4
সমাধান পদ্ধতি
সমস্যার একটি সহজ সমাধান হল নেস্টেড লুপ ব্যবহার করা। আমরা দুটি লুপ ব্যবহার করব, বাইরের একটি অ্যারের প্রতিটি পূর্ণসংখ্যা মান পুনরাবৃত্তি করতে এবং ভিতরেরটি একই মান সহ অ্যারেতে অন্য পূর্ণসংখ্যার মান আছে কিনা তা পরীক্ষা করতে। যদি হ্যাঁ, মান ফেরত দিন। এই পদ্ধতিটি ভাল কিন্তু কোন সমাধান না হলে এতে O(N2) জটিলতা থাকবে।
সমাধান পদ্ধতি
আরেকটি পদ্ধতি যা সমস্যার সমাধান করতে পারে তা হল হ্যাশিং ব্যবহার করে। আমরা শেষ সূচক থেকে অ্যারেটি অতিক্রম করব এবং তারপরে পরিদর্শন করা সূচকে পাওয়া উপাদানটির জন্য সর্বনিম্ন সূচক আপডেট করব।
উদাহরণ
আমাদের সমাধানের কাজ চিত্রিত করার জন্য প্রোগ্রাম
#include<bits/stdc++.h>
using namespace std;
int findRepeatingElementArray(int arr[], int n){
int minRetIndex = -1;
set<int> visitedElements;
for (int i = n - 1; i >= 0; i--){
if (visitedElements.find(arr[i]) != visitedElements.end())
minRetIndex = i;
else
visitedElements.insert(arr[i]);
}
if (minRetIndex != -1)
return arr[minRetIndex];
else
return -1;
}
int main(){
int arr[] = {4, 1, 6, 3, 4, 1, 5, 8};
int n = sizeof(arr) / sizeof(arr[0]);
cout<<"The element with repeated occurence is "<<findRepeatingElementArray(arr, n);
} আউটপুট
The element with repeated occurence is 4
