अंक गुम जाना


कठिनाई स्तर आसान
में अक्सर पूछा वीरांगना सेब एक राजधानी सिस्को Facebook माइक्रोसॉफ्ट
ऐरे बिट बिट मैनिपुलेशन बिट्स मठ

In अंक गुम जाना समस्या हमने दी है सरणी आकार N की संख्या 0 से N तक है। सरणी में सभी मान अद्वितीय हैं। हमें अनुपलब्ध संख्या खोजने की आवश्यकता है जो कि सरणी में मौजूद नहीं है और यह संख्या 0 से N के बीच है। यहाँ हम लापता संख्या को खोजने के लिए एक सरल दृष्टिकोण देखते हैं। हम सिर्फ उस सरणी के तत्वों का कुल योग गिनाते हैं जो हमें दिया गया है। इसके बाद, हम संख्या का योग 1 से एन तक पाते हैं और तत्व के कुल योग को उससे घटाते हैं। तब हमें नंबर नहीं मिला क्योंकि हम केवल उस संख्या को तत्वों के योग में याद करते हैं।

इनपुट प्रारूप

प्रथम-पूर्णांक जिसमें पूर्णांक मान N है।

एन-पूर्णांक मानों वाली दूसरी-पंक्ति।

आउटपुट स्वरूप

केवल एक पंक्ति जिसमें लापता संख्या है।

की कमी

  • 1 <= एन <= 1000000
  • 0 <= गिरफ्तारी [i] <= 1000000
  • इनपुट ऐरे में सभी नंबर अलग हैं।
Sample Input:
9
9 6 4 2 3 5 7 0 1
Sample Output:
8

स्पष्टीकरण: यहाँ तत्व का कुल योग = ९ + ६ + ४ + २ + ३ + ५ + + + ० + १ = ३ element है। अब हम पहले N प्राकृतिक संख्याओं का योग ज्ञात करते हैं जो N * (N + १) / २ है। तो, कुल योग = (९ * १०) / २ = ४५। अब कुल योग से तत्व का कुल योग घटाएँ। हमें 9-6 मिला है, जो कि 4. है। इनपुट ऐरे में हमारी लापता संख्या 2 है। यहाँ हम सिर्फ एक वेरिएबल माध्य का उपयोग करते हैं ओ (3) का उपयोग किया गया स्थान है।

कलन विधि

Step:1 Set elem_sum = 0.
Step:2 For i in range 0 to N-1:
           elem_sum = elem_sum+arr[i].
Step:3 Total_sum = (N*(N+1))/2
Step:4 print (Total_sum-elem_sum).

गुम संख्या के लिए कार्यान्वयन

/*C++ Implementation of "Missing Number".*/ 
#include<bits/stdc++.h> 
using namespace std; 
int main() 
{
    /*input values.*/
    int n;
    cin>>n;
    /*set elem_sum to 0*/
    int elem_sum=0;
    for(int i=0;i<n;i++)
    {
        int x;
        cin>>x;
        /*add the value of x to elem_sum*/
        elem_sum+=x;
    }
    /*print missing number.*/
    cout<<"Missing Number: ";
    cout<<(n*(n+1))/2-elem_sum<<endl;
    return 0;
}
13
0 3 2 1 5 6 7 4 9 8 10 12 13
Missing Number: 11

समय जटिलता

पर) जहां हम इनपुट लेने के लिए एक लूप का उपयोग करते हैं। इनपुट लेते समय हम तत्व योग को लगातार स्टोर करते हैं। और फिर पहले N प्राकृतिक संख्या के योग की सरल अवधारणा का उपयोग करें।

अंतरिक्ष जटिलता

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

संदर्भ