मान लीजिए हमारे पास एक संख्या p और n तत्वों वाली एक और सरणी X है। p बकेट्स के साथ एक हैश टेबल है। बकेट्स 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