주어진 배열의 하위 집합의 합계로 나타낼 수없는 가장 작은 양의 정수 값을 찾습니다.

난이도 쉽게
자주 묻는 질문 데이터 브릭 택시4슈어 UHG 옵텀
배열조회수 86

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

문제 정책

당신은 주어진 분류 정수 배열. 주어진 어떤 부분 집합의 합으로도 표현할 수없는 가장 작은 양의 정수 값을 찾아야합니다. 정렬.

arr[] = {1,4,7,8,10}
2

설명 : 2를 합계로 나타낼 수있는 하위 배열이 없기 때문입니다.

arr[] = {1,2,3,5,7,9}
28

설명 : 28를 합계로 나타낼 수있는 하위 배열이 없기 때문입니다.

 

주어진 배열의 하위 집합의 합계로 표현할 수없는 가장 작은 양의 정수 값을 찾는 알고리즘

1. Set output to 1.
2. From i=0 to i less than n.
  1. Check if arr[i] is less than equal to output.
    1. Update the value of output to the sum of output and arr[i].
3. Return output.

 

설명

주어진 배열의 하위 집합의 합계로 나타낼 수없는 가장 작은 양의 정수 값을 찾습니다.

 

 

정렬 된 정수 배열이 제공됩니다. 문제 설명은 가장 작은 양의 정수 값을 찾을 것을 요청합니다. 주어진 배열의 하위 집합의 합계로 나타낼 수 없습니다. 이 솔루션을 선형으로 찾을 수 있습니다. 시간 복잡성 의 위에). 이미 정렬 된 배열이 있습니다. 따라서 우리는 선형 시간에서 이것을 찾을 수있는 이유 인 순서 또는 숫자 차이에 대해 걱정할 필요가 없습니다.

우리는 배열을 횡단 할 것입니다. 그러나 적어도 가장 작은 양의 정수가 있으므로 그 전에 출력 값을 1로 설정하십시오. 1부터 시작하는 배열이 없으면 출력 값으로 1을 반환합니다. 따라서 출력 값을 1로 설정 한 후 배열을 순회합니다. 배열의 첫 번째 요소를 선택하고 출력 값보다 작거나 같은지 확인합니다. 참이면 출력 값과 현재 배열 요소를 더합니다. 그리고 이것을 출력에 저장하십시오. 배열 요소의 값이 출력 값보다 크지 않을 때까지이 작업을 계속합니다. 그런 다음 루프에서 나오고 출력 값을 반환합니다.

예를 arr [] = {1,4,7,8,10}으로 가정하면 output = 1로 시작하고 첫 번째 요소를 계속 선택하여 출력보다 작거나 같은지 확인합니다. , 그것은 참이고 우리는 output과 arr [i]의 값을 더하고 그것을 output에 저장할 것입니다. 그리고 우리는 이제 2를 출력에 가지고 있습니다. 다시 우리는 값을 확인하지만 이제 배열의 모든 값이 출력보다 작거나 같지 않으므로 마지막으로 2가 필수 답변이고 반환 할 것입니다.

주어진 배열의 하위 집합의 합계로 나타낼 수없는 가장 작은 양의 정수 값을 찾는 코드

C ++ 코드

#include<iostream>

using namespace std;

int getSmallestInteger(int arr[], int n)
{
    int output = 1;
    for (int i = 0; i < n && arr[i] <= output; i++)
        output = output + arr[i];

    return output;
}
int main()
{
    int arr[] = {1, 3, 4, 5};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout <<"Smallest positive integer : "<<getSmallestInteger(arr, n);

    return 0;
}
Smallest positive integer : 2

 

자바 코드

class IntegernotSumofSubArray
{
    public static int getSmallestInteger (int arr[], int n)
    {
        int output = 1;

        for (int i = 0; i < n && arr[i] <= output; i++)
            output = output + arr[i];

        return output;
    }
    public static void main(String[] args)
    {
        int arr[] = {1, 3, 4, 5};
        int n = arr.length;
        System.out.println("Smallest positive integer : "+getSmallestInteger (arr, n));
    }
}
Smallest positive integer : 2

 

복잡성 분석

배열의 하위 집합 합계로 존재하지 않는 가장 작은 양수 값을 찾기위한 시간 복잡성

단순히 배열을 순회 할 때마다 선형 시간 복잡도 연산을 수행합니다. 그리고 여기서 우리는 단일 순회 만 수행하기 때문에 선형 시간 복잡성을가집니다. O (N) 어디에 "엔"  배열의 요소 수입니다.

배열의 하위 집합 합계로 존재하지 않는 가장 작은 양수 값을 찾기위한 공간 복잡성

우리는 단순히 입력을 저장하는 단일 배열을 가지므로 알고리즘도 선형 공간 복잡성을 갖습니다. O (N) 어디에 "엔"  배열의 요소 수입니다.

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