Nömrə yoxdur

Çətinlik səviyyəsi Asan
Tez-tez soruşulur Amazon alma Capital One Cisco Facebook microsoft
Geyim Parça Bit manipulyasiya Bits RiyaziyyatBaxılıb 59

Sistem dizaynı ilə bağlı müsahibə sualları o qədər açıq ola bilər ki, düzgün hazırlaşmağı bilmək çox çətindir. İndi satın aldıqdan sonra Amazon, Microsoft və Adobe-nin dizayn dövrlərini sındıra bilirəm Bu kitabı. Gündəlik bir yenidən nəzərdən keçirin dizayn sualı və söz verirəm ki, dizayn dövrünü sındıra bilərsiniz.

In Nömrə yoxdur problem verdik array 0-dan N-ə qədər bir ədədi ehtiva edən N ölçülü massivdəki bütün dəyərlər unikaldır. Massivdə olmayan itkin nömrəni tapmaq lazımdır və bu rəqəm 0 ilə N arasındadır. Burada itkin sayın tapılması üçün sadə bir yanaşma görürük. Yalnız serialın bizə verilən elementlərinin ümumi cəmini hesablayırıq. Bundan sonra, 1-dən N-ə qədər olan ədədin cəmini tapırıq və ondan elementin ümumi cəmini çıxardırıq. Sonra rəqəmi yalnız elementlərin cəmində darıxdığımız üçün əldə etmədik.

Giriş Formatı

Bir tam dəyər N ehtiva edən birinci sətir.

N tam ədədi olan ikinci sətir.

Çıxış formatı

İtkin nömrəni ehtiva edən yalnız bir sətir.

Məhdudiyyətlər

  • 1 <= N <= 1000000
  • 0 <= arr [i] <= 1000000
  • Giriş massivindəki bütün nömrələr fərqlidir.
Sample Input:
9
9 6 4 2 3 5 7 0 1
Sample Output:
8

Explanation: Burada elementin cəmi = 9 + 6 + 4 + 2 + 3 + 5 + 7 + 0 + 1 = 37. İndi N * (N + 1) / 2 olan ilk N natural ədədin cəmini tapırıq. Beləliklə, ümumi cəmi = (9 * 10) / 2 = 45. İndi elementin cəmi cəmini cəmdən çıxarın. 45-37 əldə etdik, bu 8-dir. Beləliklə giriş sıra içindəki itkin sayımız 8-dir. Burada yalnız bir dəyişən istifadə edir o (1) istifadə olunan boşluq deməkdir.

Alqoritm

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).

İtkin nömrə üçün tətbiqetmə

/*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

Zamanın mürəkkəbliyi

O (N) giriş götürmək üçün bir döngədən istifadə etdiyimiz yer. Giriş götürərkən element cəmini davamlı olaraq saxlayırıq. Və sonra ilk N təbii ədədin cəminin sadə konsepsiyasından istifadə edin.

Kosmik Mürəkkəblik

O (1) çünki əlavə yer istifadə etmirik və yalnız dəyişənlərdən istifadə edərək giriş edirik. Burada massivdə mövcud olan bütün elementlərin cəmini saxlayan dəyişəndən istifadə edirik. Başqa bir dəyişən 1-dən N-ə qədər olan bütün elementlərin cəmini saxlayır. Bu dəyişənlərdən istifadə edərək yalnız itkin rəqəmi tapırıq.

References

Crack Sistemi Dizayn Müsahibələri
Translate »