अवधारणा
दो दी गई सरणियों के संबंध में जो एक तत्व को छोड़कर एक-दूसरे की डुप्लिकेट हैं, इसका मतलब है कि एक सरणी से एक तत्व गायब है, हमारा कार्य उस गायब तत्व को निर्धारित करना है।
इनपुट
arr1[] = {2, 5, 6, 8, 10} arr2[] = {5, 6, 8, 10}आउटपुट
2
2 दूसरी सरणी से गायब है।
इनपुट
arr1[] = {3, 4, 5, 6} arr2[] = {3, 4, 5, 6, 7}आउटपुट
7
7 पहली सरणी से गायब है।
विधि
यहां, हम एक सरल समाधान लागू करते हैं जहां हम सरणियों पर पुनरावृति करते हैं और तत्व दर तत्व सत्यापित करते हैं और जब एक बेमेल का पता चलता है तो गायब तत्व को चिह्नित करते हैं। लेकिन इस समाधान की कमी यह है कि इसके लिए सरणी के आकार पर रैखिक समय की आवश्यकता होती है।
हम एक और कुशल समाधान लागू कर सकते हैं जो बाइनरी खोज दृष्टिकोण पर आधारित है। हम नीचे दिए गए एल्गोरिदम का पालन करते हैं जिसे चरण दर चरण समझाया गया है −
- बड़े सरणी में बाइनरी खोज शुरू करें और mid को (low + high) / 2 के रूप में प्राप्त करें
- यह देखा गया है कि यदि दोनों सरणी से मान समान है तो गायब तत्व दाहिने भाग में होना चाहिए इसलिए low को mid के रूप में चिह्नित करें
- अन्यथा high को mid के रूप में चिह्नित करें क्योंकि यदि mid तत्व समान नहीं है तो गायब तत्व बड़े सरणी के बाएं भाग में होना चाहिए।
- हमें विशेष मामले को अलग से संभालना होगा क्योंकि एकल तत्व और शून्य तत्व सरणी के लिए, एकल तत्व स्वयं गायब तत्व होगा।
यह देखा गया है कि यदि पहला तत्व स्वयं बराबर नहीं है तो वह तत्व गायब तत्व होगा।
उदाहरण
// C++ program to find missing element from same // arrays (except one missing element) #include <bits/stdc++.h> using namespace std; // बाइनरी खोज दृष्टिकोण के आधार पर गायब तत्व निर्धारित करने वाला फ़ंक्शन। arrA[] बड़े आकार का है और // Q इसका आकार है। arrA[] और arrB[] माने जाते हैं // समान क्रम में। int findMissingUtil(int arrA[], int arrB[], int Q){ // विशेष मामले पर विचार करें, केवल तत्व के लिए जो // दूसरी सरणी में गायब है if (Q == 1) return arrA[0]; // विशेष मामले पर विचार करें, पहले तत्व के गायब होने के लिए if (arrA[0] != arrB[0]) return arrA[0]; // वर्तमान कोने बिंदुओं को इनिशियलाइज़ करने के लिए उपयोग किया जाता है int low = 0, high = Q - 1; // low < high तक पुनरावृति करें while (low < high){ int mid = (low + high) / 2; // यह देखा गया है कि यदि mid सूचकांकों पर तत्व बराबर हैं // तो दाएं उपसरणी पर जाएं if (arrA[mid] == arrB[mid]) low = mid; else high = mid; // इसलिए यदि low, high सन्निकट हो जाते हैं, तो ब्रेक करें if (low == high - 1) break; } // अब गायब तत्व बड़े सरणी के // high सूचकांक पर होगा return arrA[high]; } // तो यह फ़ंक्शन मुख्य रूप से बुनियादी त्रुटि जांच करता है // और findMissingUtil को कॉल करता है void findMissing(int arrA[], int arrB[], int P, int Q){ if (Q == P-1) cout << "Missing Element is " << findMissingUtil(arrA, arrB, P) << endl; else if (P == Q-1) cout << "Missing Element is " << findMissingUtil(arrB, arrA, Q) << endl; else cout << "Invalid Input"; } // ड्राइवर कोड int main(){ int arrA[] = {2, 5, 6, 8, 10}; int arrB[] = {5, 6, 8, 10}; int P = sizeof(arrA) / sizeof(int); int Q = sizeof(arrB) / sizeof(int); findMissing(arrA, arrB, P, Q); return 0; }आउटपुट
Missing Element is 2
