এখানে আমরা দেখব কিভাবে চেক করা যায় যে সাজানো না করা অ্যারেতে একে অপরের থেকে k দূরত্বের মধ্যে ডুপ্লিকেট উপাদান আছে কি না। ধরুন উপাদানগুলির একটি তালিকা হল {1, 2, 3, 1, 4, 5}, এখানে যদি k =3 হয়, তাহলে প্রোগ্রামটি সত্য হবে, কারণ দুটি 1s-এর মধ্যে দূরত্ব হল 3৷
আমরা একটি হ্যাশ টেবিল ব্যবহার করে এটি সমাধান করব। ধাপগুলো নিচের মত হবে -
- একটি খালি হ্যাশ টেবিল তৈরি করুন
- প্রতিটি সূচক i এর জন্য, তালিকায় উপাদান e =arr[i] দিন, করুন
- হ্যাশ টেবিলে যদি ই উপস্থিত থাকে, তাহলে সত্য ফেরত দিন
- অন্যথায়, হ্যাশ টেবিলে e যোগ করুন এবং হ্যাশ টেবিল থেকে (i-k)তম উপাদানটি যদি বিদ্যমান থাকে, যখন i>=K।
উদাহরণ
#include<iostream>
#include<set>
using namespace std;
bool hasDuplicateWithDistK(int arr[], int n, int k) {
set<int> element_set;
for (int i = 0; i < n; i++) {
if (element_set.find(arr[i]) != element_set.end())
return true;
element_set.insert(arr[i]);
if (i >= k)
element_set.erase(arr[i-k]);
}
return false;
}
int main () {
int arr[] = {10, 5, 3, 4, 3, 5, 6};
int n = sizeof(arr) / sizeof(arr[0]);
if (hasDuplicateWithDistK(arr, n, 3))
cout << "Duplicate element has found";
else
cout << "Duplicate element has not found";
} আউটপুট
Duplicate element has found
