Brakujący numer

Poziom trudności Łatwo
Często zadawane pytania Amazonka Apple Capital One Cisco Facebook Microsoft
Szyk Bit Manipulacja bitami Bity matematykaodwiedzajacy 59

Pytania do rozmowy kwalifikacyjnej na temat projektowania systemu może być tak nieograniczona, że ​​trudno jest określić właściwy sposób przygotowania. Teraz jestem w stanie złamać rundy projektowe Amazon, Microsoft i Adobe po zakupie ta książka. Codziennie poprawiaj jeden pytanie projektowe i obiecuję, że możesz złamać cały projekt.

In Brakujący numer problem, który daliśmy szyk o rozmiarze N zawierający liczbę od 0 do N. Wszystkie wartości w tablicy są unikalne. Musimy znaleźć brakującą liczbę, której nie ma w tablicy, a ta liczba znajduje się między 0 a N. Tutaj widzimy proste podejście do znalezienia brakującej liczby. Po prostu liczymy całkowitą sumę elementów tablicy, która jest nam podana. Następnie znajdujemy sumę liczby od 1 do N i odejmujemy od niej całkowitą sumę elementu. Następnie otrzymaliśmy liczbę nieobecną, ponieważ brakuje nam tej liczby tylko w sumie elementów.

Format wejściowy

Pierwszy wiersz zawierający liczbę całkowitą N.

Drugi wiersz zawierający N wartości całkowitych.

Format wyjściowy

Tylko jeden wiersz zawierający brakującą liczbę.

ograniczenia

  • 1 <= N <= 1000000
  • 0 <= arr [i] <= 1000000
  • Wszystkie liczby w tablicy wejściowej są różne.
Sample Input:
9
9 6 4 2 3 5 7 0 1
Sample Output:
8

Wyjaśnienie: Tutaj suma elementów = 9 + 6 + 4 + 2 + 3 + 5 + 7 + 0 + 1 = 37. Teraz znajdujemy sumę pierwszych N liczb naturalnych, która wynosi N * (N + 1) / 2. Zatem suma całkowita = (9 * 10) / 2 = 45. Teraz odejmij całkowitą sumę elementu od sumy całkowitej. Otrzymaliśmy 45-37, czyli 8. Więc nasza brakująca liczba w tablicy wejściowej to 8. Tutaj używamy tylko jednej zmiennej, co oznacza, że ​​o (1) jest wykorzystaną przestrzenią.

Algorytm

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

Wdrożenie dla brakującego numeru

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

Złożoność czasowa

NA) gdzie używamy jednej pętli do pobierania danych wejściowych. Podczas wprowadzania danych przechowujemy sumę elementów w sposób ciągły. Następnie użyj prostego pojęcia sumy pierwszej liczby naturalnej N.

Złożoność przestrzeni

O (1) ponieważ nie używamy dodatkowej przestrzeni i po prostu pobieramy dane wejściowe za pomocą zmiennych. Tutaj używamy zmiennej, która przechowuje sumę wszystkich elementów obecnych w tablicy. Inna zmienna przechowuje sumę wszystkich elementów od 1 do N. Używając tylko tych zmiennych, znajdujemy brakującą liczbę.

Referencje

Wywiady dotyczące projektowania systemu pękania
Translate »