எண் இல்லை


சிரமம் நிலை எளிதாக
அடிக்கடி கேட்கப்படுகிறது அமேசான் ஆப்பிள் மூலதன ஒன்று சிஸ்கோ பேஸ்புக் மைக்ரோசாப்ட்
அணி பிட் பிட் கையாளுதல் பிட்ஸ் கணித

In எண் இல்லை நாங்கள் கொடுத்த பிரச்சினை வரிசை 0 முதல் N வரையிலான எண்ணைக் கொண்ட N அளவு. வரிசையில் உள்ள அனைத்து மதிப்புகளும் தனித்துவமானது. வரிசையில் இல்லாத காணாமல் போன எண்ணை நாம் கண்டுபிடிக்க வேண்டும், அந்த எண் 0 முதல் N வரை உள்ளது. காணாமல் போன எண்ணைக் கண்டுபிடிப்பதற்கான எளிய அணுகுமுறையை இங்கே காண்கிறோம். எங்களுக்கு வழங்கப்பட்ட வரிசையின் உறுப்புகளின் மொத்த தொகையை நாங்கள் கணக்கிடுகிறோம். இதற்குப் பிறகு, எண்ணின் கூட்டுத்தொகையை 1 முதல் N வரை கண்டுபிடித்து, அதிலிருந்து தனிமத்தின் மொத்தத் தொகையைக் கழிப்போம். உறுப்புகளின் கூட்டுத்தொகையில் மட்டுமே அந்த எண்ணை இழப்பதால் எண்ணைக் காணவில்லை.

உள்ளீட்டு வடிவம்

ஒரு முழு எண் மதிப்பைக் கொண்ட முதல் வரி N.

N முழு எண் மதிப்புகளைக் கொண்ட இரண்டாவது வரி.

வெளியீட்டு வடிவம்

விடுபட்ட எண்ணைக் கொண்ட ஒரே ஒரு வரி.

தடைகள்

  • 1 <= N <= 1000000
  • 0 <= arr [i] <= 1000000
  • உள்ளீட்டு வரிசையில் உள்ள அனைத்து எண்களும் வேறுபட்டவை.
Sample Input:
9
9 6 4 2 3 5 7 0 1
Sample Output:
8

விளக்கம்: இங்கே தனிமத்தின் மொத்த தொகை = 9 + 6 + 4 + 2 + 3 + 5 + 7 + 0 + 1 = 37. இப்போது முதல் N இயற்கை எண்களின் கூட்டுத்தொகையை N * (N + 1) / 2 என்று காணலாம். எனவே, மொத்த தொகை = (9 * 10) / 2 = 45. இப்போது தனிமத்தின் மொத்தத் தொகையை மொத்தத் தொகையிலிருந்து கழிக்கவும். எங்களுக்கு 45-37 கிடைத்தது 8 ஆகும். எனவே உள்ளீட்டு வரிசையில் நம் காணாமல் போன எண் 8 ஆகும். இங்கே நாம் ஒரு மாறி வழியைப் பயன்படுத்துகிறோம் o (1) என்பது பயன்படுத்தப்படும் இடம்.

அல்காரிதம்

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 முதல் N வரையிலான அனைத்து உறுப்புகளின் கூட்டுத்தொகையை சேமிக்கிறது. இந்த மாறிகளைப் பயன்படுத்தி காணாமல் போன எண்ணைக் காணலாம்.

குறிப்புகள்