जांचें कि दिए गए उत्पाद के साथ एक जोड़ी सी ++ में लिंक्ड सूची में मौजूद है या नहीं

हमारे पास तत्वों का एक सेट है। और एक उत्पाद K. कार्य यह जाँचना है कि क्या लिंक की गई सूची में दो संख्याएँ मौजूद हैं, जिनका उत्पाद K के समान है। यदि दो संख्याएँ हैं, तो उन्हें प्रिंट करें, यदि दो से अधिक संख्याएँ हैं, तो उनमें से कोई भी प्रिंट करें . मान लीजिए कि लिंक की गई सूची इस तरह है {2, 4, 8, 12, 15}, और k मान 16 है। तो यह वापस आ जाएगा (2, 8)

हम हैशिंग तकनीक का उपयोग करके इसे हल करेंगे। एक हैश तालिका लें, और सभी तत्वों को 0 के रूप में चिह्नित करें। अब सभी तत्वों को हैश तालिका में 1 के रूप में चिह्नित करें, यदि वह लिंक की गई सूची में मौजूद है। अब लिंक की गई सूची का पता लगाना शुरू करें, और जांचें कि दिया गया उत्पाद वर्तमान तत्व से विभाज्य है या नहीं। यदि हाँ, तो जांचें कि लिंक्ड सूची का (K/वर्तमान तत्व) हैश तालिका में मौजूद है या नहीं।

उदाहरण

#include <unordered_set>
#define MAX 100000
using namespace std;
class Node {
   public:
   int data;
   Node* next;
};
void append(struct Node** start, int key) {
   Node* new_node = new Node;
   new_node->data = key;
   new_node->next = (*start);
   (*start) = new_node;
}
bool isPairPresent(Node* start, int K) {
   unordered_set<int> s;
   Node* p = start;
   while (p != NULL) {
      int current = p->data;
      if ((K % current == 0) && (s.find(K / current) != s.end())) {
         cout << current << " " << K / current;
         return true;
      }
      s.insert(p->data);
      p = p->next;
   }
   return false;
}
int main() {
   Node* start = NULL;
   int arr[] = {2, 4, 8, 12, 15};
   int n = sizeof(arr)/sizeof(arr[0]);
   for(int i = 0; i<n; i++){
      append(&start, arr[i]);
   }
   if (isPairPresent(start, 16) == false)
   cout << "NO PAIR EXIST";
}

आउटपुट

2 8