सी ++ कोड इंडेक्स खोजने के लिए जहां यह हैश टकराव है

मान लीजिए कि हमारे पास n तत्वों के साथ एक संख्या p और एक अन्य सरणी X है। पी बाल्टी के साथ एक हैश टेबल है। बाल्टियों की संख्या 0 से p-1 तक होती है। हम एक्स से एन नंबर डालना चाहते हैं। हम एक्स [i] के लिए मान रहे हैं, इसकी बाल्टी हैश फ़ंक्शन एच (एक्स [i]) द्वारा चुनी जाएगी, जहां एच (के) =के मॉड पी। एक बाल्टी में एक से अधिक तत्व नहीं हो सकते। यदि हम पहले से भरी हुई बाल्टी में एक संख्या डालना चाहते हैं, तो हम कहते हैं कि एक "टकराव" होता है। हमें उस इंडेक्स को वापस करना होगा जहां टक्कर हुई है। अगर कोई टक्कर नहीं है, तो -1 लौटें।

इसलिए, यदि इनपुट p =10 जैसा है; एक्स =[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 }