Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

C++ में 1 से N तक के तत्वों वाली सरणी में चार गायब संख्याएं खोजें


अवधारणा

एक दी गई अद्वितीय पूर्णांकों की सरणी के संबंध में जहां दी गई सरणी का प्रत्येक पूर्णांक रेंज [1, N] में स्थित है, सरणी का आकार (N-4) है और कोई एकल तत्व दोहराया नहीं गया है। तो, 1 से N तक चार संख्याएं सरणी में गायब हैं। क्रमबद्ध क्रम में 4 गायब संख्याएं निर्धारित करें।

इनपुट

arr[] = {3, 6, 7, 4, 10}

आउटपुट

1 2 5 8 9

इनपुट

arr[] = { 2, 8, 4, 13, 6, 11, 9, 5, 10 }

आउटपुट

1 3 7 12

विधि

अब एक सरल O(N) समाधान है कि N आकार की एक सहायक सरणी लागू करें ताकि देखे गए तत्वों को इंगित या चिह्नित किया जा सके। इनपुट सरणी पर जाएं और सहायक सरणी में तत्वों को इंगित या चिह्नित करें। अंत में उन सभी इंडेक्स को प्रिंट करें जो इंगित या चिह्नित नहीं हैं।

अब सवाल उठता है कि O(1) सहायक स्थान के साथ कैसे हल करें?

सबसे पहले हम हेल्पर नामक एक सरणी को लंबाई 4 के साथ इनिशियलाइज़ करते हैं ताकि 4 गायब संख्याओं की भरपाई की जा सके और उन्हें शून्य से भरें। उसके बाद हम i=0 से i < दी गई सरणी की लंबाई तक पुनरावृति करते हैं और i-वें तत्व का निरपेक्ष मान लेकर एक वेरिएबल टेम्प में संग्रहीत करते हैं। इस समय, हम सत्यापित करेंगे −

<उल क्लास="सूची"><ली>

यह देखा गया है कि यदि तत्व का निरपेक्ष मान इनपुट सरणी की लंबाई से छोटा है तो हम सरणी[टेम्प] तत्व को -1 से गुणा करेंगे (देखे गए तत्व को इंगित या चिह्नित करने के क्रम में)।

<ली>

यह देखा गया है कि यदि तत्व का निरपेक्ष मान इनपुट सरणी की लंबाई से बड़ा है तो हम हेल्पर[टेम्प%सरणी.लंबाई] तत्व के मान को -1 से रखेंगे (देखे गए तत्व को इंगित या चिह्नित करने के क्रम में)।

अब हम इनपुट सरणी पर पुनरावृति करते हैं और वे इंडेक्स जिनका मान अभी भी शून्य से बड़ा है तो वे तत्व इनपुट सरणी में नहीं मिले। इसके परिणामस्वरूप हम (इंडेक्स+1) मान प्रिंट करते हैं जिस इंडेक्स का तत्व शून्य से बड़ा है।

अब हम हेल्पर सरणी पर पुनरावृति करेंगे और वे इंडेक्स जिनका मान अभी भी शून्य से बड़ा है तो वे तत्व इनपुट सरणी में नहीं मिले। इसके परिणामस्वरूप हम (इंडेक्स+सरणी.लंबाई+1) मान प्रिंट करते हैं जिस इंडेक्स का तत्व शून्य से बड़ा है।

उदाहरण

<प्रि क्लास="प्रिटीप्रिंट नोट्रांसलेट">// CPP program to find missing 4 elements // in an array of size N where elements are // in range from 1 to N+4. #include <bits/stdc++.h> using namespace std; // O(N) समय और O(1) सहायक स्थान में गायब 4 संख्याएं खोजने के लिए उपयोग किया जाता है। void missing4(int arr1[], int n1){    // 4 संभावित संख्याओं का ट्रैक रखने के लिए उपयोग किया जाता है    // जो इनपुट सरणी की लंबाई से बड़ी हैं    // जावा के मामले में, हेल्पर स्वचालित रूप से    // 0 के रूप में इनिशियलाइज़ होता है।    int helper[4];    // इनपुट सरणी पर जाएं और    // देखे गए तत्वों को या तो arr[] में ऋणात्मक के रूप में चिह्नित करके    // या हेल्पर[] में चिह्नित करें।    for (int i = 0; i < n1; i++) {       int temp1 = abs(arr1[i]);       // यह देखा गया है कि यदि तत्व छोटा है या       // लंबाई के बराबर है, तो इसकी       // उपस्थिति को arr1[] में चिह्नित करें       if (temp1 <= n1)          arr1[temp1 - 1] *= (-1);       // हेल्पर[] में उपस्थिति इंगित या चिह्नित करें       else if (temp1 > n1) {          if (temp1 % n1 != 0)             helper[temp1 % n1 - 1] = -1;          else             helper[(temp1 % n1) + n1 - 1] = -1;       }    }    // उन सभी तत्वों को प्रिंट करने के लिए उपयोग किया जाता है जिनकी उपस्थिति    // चिह्नित नहीं है।    for (int i = 0; i < n1; i++)       if (arr1[i] > 0)          cout << (i + 1) << " ";    for (int i = 0; i < 4; i++)       if (helper[i] >= 0)          cout << (n1 + i + 1) << " ";       return; } // ड्राइवर कोड int main(){    int arr1[] = { 2, 8, 4, 13, 6, 11, 9, 5, 10 };    int n1 = sizeof(arr1) / sizeof(arr1[0]);    missing4(arr1, n1);    return 0; }

आउटपुट

1 3 7 12

  1. - C++ में दिए गए सरणी के एलिमेंट्स के फैक्टोरियल का GCD खोजें

    मान लीजिए हमारे पास N एलिमेंट्स वाली एक सरणी A है। हमें सरणी के सभी एलिमेंट्स के फैक्टोरियल का GCD निकालना है। मान लीजिए एलिमेंट्स {3, 4, 8, 6} हैं, तो फैक्टोरियल का GCD 6 होगा। यहां हम ट्रिक देखेंगे। चूंकि दो संख्याओं का GCD वह सबसे बड़ी संख्या है जो दोनों को विभाजित करती है, तो दो संख्याओं के फैक्

  1. - PHP में सरणी से लापता तत्व ढूँढने का प्रोग्राम

    PHP में array_diff() और range() फ़ंक्शन्स का उपयोग करके एक संख्यात्मक सरणी में लापता (missing) तत्वों को आसानी से ढूंढा जा सकता है। उदाहरण <?php function absent($my_list) { $my_array = range(min($my_list), max($my_list)); return array_diff($my_array, $my_list); } echo Elements missing f

  1. - Python में 1 से N तक के तत्वों वाली सरणी में चार लापता संख्याएं ढूंढना

    मान लीजिए हमारे पास अलग-अलग संख्याओं की एक सरणी है जहां प्रत्येक संख्या [1, N] सीमा में है, सरणी का आकार (N-4) है और कोई एकल तत्व दोहराया नहीं गया है। तो, हम समझ सकते हैं कि 1 से N तक चार संख्याएं सरणी में गायब हैं। हमें इन 4 लापता संख्याओं को क्रमबद्ध तरीके से ढूंढना है। तो, यदि इनपुट A =[2, 8, 4,