누락 된 번호

난이도 쉽게
자주 묻는 질문 아마존 Apple 자본 하나 시스코 Facebook Microsoft
배열 비트 비트 조작 비트 수학조회수 58

시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.

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 + 1) / 2 인 처음 N 개의 자연수의 합을 찾습니다. 따라서 총합은 (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 자연수의 합이라는 간단한 개념을 사용하십시오.

공간 복잡성

O (1) 추가 공간을 사용하지 않고 변수를 사용하여 입력을 받기 때문입니다. 여기서 우리는 배열에있는 모든 요소의 합을 저장하는 변수를 사용합니다. 또 다른 변수는 1부터 N까지의 모든 요소의 합을 저장합니다.이 변수를 사용하여 누락 된 숫자 만 찾습니다.

참조

균열 시스템 설계 인터뷰
Translate »