মান লক্ষ্য করুন একটি সংখ্যা p এবং আরেকটি n এলিমেন্টের অ্যারে X। p বাকেটের একটি হ্যাশ টেবিল আছে। বাকেটগুলো ০ থেকে p-1 নম্বর করা আছে। আমরা X থেকে n টি নম্বর ইনসার্ট করতে চাই। আমরা অনুমান করছি X[i]-র জন্য, এর বাকেট হ্যাশ ফাংশন h(X[i]) দ্বারা সিলেক্ট হবে, যেখানে h(k) = k mod p। একটি বাকেট একাধিক এলিমেন্ট ধারণ করতে পারবে না। যদি আমরা একটি নম্বর একই বাকেটে ইনসার্ট করতে চাই যা ইতিমধ্যে ভরা আছে, তবে আমরা বলি একটি "কলিশন" ঘটেছে। আমাদের কলিশন ঘটেছে সে ইনডেক্স রিটার্ন করতে হবে। যদি কোনো কলিশন না থাকে, তবে -1 রিটার্ন করুন।
তাই, যদি ইনপুট হয় p = 10; X = [0, 21, 53, 41, 53], তবে আউটপুট হবে ৩, কারণ প্রথমটি ০-এ ইনসার্ট হবে, দ্বিতীয়টি ১-এ, তৃতীয়টি ৩-এ, কিন্তু চতুর্থটি ১-এ ইনসার্ট করার চেষ্টা করবে কিন্তু কলিশন হবে, ইনডেক্স ৩ এখানে।
ধাপসমূহ
এটি সমাধান করার জন্য, আমরা এই ধাপগুলো অনুসরণ করব −
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
