ধরুন আমাদের একটি সংখ্যা p এবং n উপাদান সহ আরেকটি অ্যারে X আছে। পি buckets সঙ্গে একটি হ্যাশ টেবিল আছে. বালতিগুলি 0 থেকে p-1 পর্যন্ত সংখ্যাযুক্ত। আমরা X থেকে n সংখ্যা সন্নিবেশ করতে চাই। আমরা X[i] এর জন্য ধরে নিচ্ছি, এর বালতি হ্যাশ ফাংশন h(X[i]) দ্বারা নির্বাচন করা হবে, যেখানে h(k) =k mod p. একটি বালতি একাধিক উপাদান ধারণ করতে পারে না। যদি আমরা ইতিমধ্যেই ভরা একটি বালতিতে একটি সংখ্যা সন্নিবেশ করতে চাই, আমরা বলি একটি "সংঘর্ষ" ঘটে। যেখানে সংঘর্ষ হয়েছে সেই সূচকটি আমাদের ফিরিয়ে দিতে হবে। যদি কোন সংঘর্ষ না হয়, -1 ফেরত দিন।
সুতরাং, যদি ইনপুট হয় p =10; X =[0, 21, 53, 41, 53], তাহলে আউটপুট 3 হবে, কারণ প্রথমটি 0 তে, দ্বিতীয়টি 1 এ, তৃতীয়টি 3 এ প্রবেশ করানো হবে, তবে চতুর্থটি 1 তে সন্নিবেশ করার চেষ্টা করবে কিন্তু একটি সংঘর্ষ আছে, সূচক এখানে 3।
পদক্ষেপ
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
n := size of X Define an array arr of size: p and fill with 0 for initialize i := 0, when i < n, update (increase i by 1), do: x := X[i] if arr[x mod p] is non-zero, then: return i increase arr[x mod p] by 1 return -1
উদাহরণ
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
#include <bits/stdc++.h>
using namespace std;
int solve(int p, vector<int> X){
int n = X.size();
int arr[p] = { 0 };
for (int i = 0; i < n; i++){
int x = X[i];
if (arr[x % p]){
return i;
}
arr[x % p]++;
}
return -1;
}
int main(){
int p = 10;
vector<int> X = { 0, 21, 53, 41, 53 };
cout << solve(p, X) << endl;
} ইনপুট
10, { 0, 21, 53, 41, 53 } আউটপুট
3
