시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 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까지의 모든 요소의 합을 저장합니다.이 변수를 사용하여 누락 된 숫자 만 찾습니다.
