주어진 범위의 요소를 제외한 배열의 모든 수에 대한 GCD 쿼리


난이도 하드
자주 묻는 질문 아마존 자본 하나 DE Shaw 구글 페이팔 Quora 테라 데이타
배열 동적 프로그래밍 GCD 수학 쿼리 문제

문제 정책

"주어진 범위의 요소를 제외한 배열의 모든 수에 대한 GCD 쿼리"문제는 정수 정렬q 쿼리 수. 각 쿼리에는 왼쪽과 오른쪽 숫자가 포함됩니다. 문제 설명은 주어진 쿼리 범위 내를 제외한 모든 정수의 최대 공약수를 알아 내도록 요청합니다.

arr[] = {1, 3, 6, 9}
Query: {(2, 3), (0, 1), (1, 2)}
1 3 1

설명

인덱스 2에서 3까지의 요소를 제외한 요소의 GCD, 즉 1과 3의 GCD는 1입니다.

이제 인덱스 0에서 1까지의 요소를 제외한 요소의 GCD는 6과 9의 GCD가 3입니다.

다시 색인 1에서 2까지의 요소를 제외한 요소의 GCD, 즉 1과 9의 GCD는 1입니다.

주어진 범위의 요소를 제외한 배열의 모든 수에 대한 GCD 쿼리

 

암호알고리즘

  1. 주어진 입력 배열과 같은 크기의 배열 두 개를 만듭니다.
  2. 1 인덱스에서 배열 길이까지 배열을 순회합니다. 그런 다음 preArray의 이전 인덱스에 저장된 현재 요소와 요소의 GCD를 찾아 preArray의 현재 인덱스에 저장합니다.
  3. 배열을 오른쪽에서 왼쪽으로 순회하고 suffixArray 요소와 주어진 배열 요소의 GCD를 찾아 GCD를 suffixArray에 저장합니다.
  4. 주어진 각 쿼리에 대해 왼쪽 범위가 0이면 suffixArray [right + 1] 값을 반환합니다.
  5. 그렇지 않으면 right 값이 n – 1과 같으면 preArray [left – 1] 값을 반환합니다.
  6. 그렇지 않으면 preArray [left-1] 및 suffixArray [right + 1]의 GCD 값을 반환합니다.

설명

대답 할 정수 및 쿼리 배열이 제공됩니다. 우리는 최대 공약수 주어진 쿼리 범위에있는 모든 정수를 제외한 숫자의. 길이가 0 인 배열에서 1에서 5 사이의 범위가 주어지면 배열에서 arr [0]과 arr [1]을 제외한 모든 정수의 최대 공약수를 찾아야합니다. 왼쪽과 오른쪽을 범위로 포함하는 쿼리가 제공됩니다. 이 범위에있는 정수는 그대로 두어야합니다.

우리는 배열을 순회 할 것이지만 그 전에 주어진 배열의 첫 번째 요소를 preArray의 첫 번째 요소로 복사합니다. 그 후 왼쪽에서 오른쪽으로 배열을 횡단합니다. 이 시간 동안 우리는 preArray와 suffixArray를 만들 것입니다. preArray의 경우 원래 입력 배열의 현재 인덱스에있는 요소와 preArray의 이전 인덱스에있는 요소의 최대 공약수를 찾습니다. 이 숫자의이 GCD를 preArray 요소에 저장하십시오. 배열을 탐색 한 후 suffixArray를 빌드합니다. 이를 위해 suffixArray의 마지막 요소 위치에 있습니다. 주어진 배열 요소 배열의 마지막 요소를 복사합니다. 그 후 preArray에 대해 수행하는 것과 동일한 절차를 따르지만 배열의 오른쪽에서 왼쪽으로.

주어진 범위의 주어진 각 쿼리에 대해 주어진 왼쪽 범위가 0과 같은지 확인합니다. 따라서 suffixArray [right + 1]의 값을 반환합니다. right 값이 배열의 길이와 같은지 확인하십시오. 그런 다음 preArray [left -1]의 값을 반환합니다. Else는 preArray의 왼쪽 인덱스에있는 요소와 suffixArray의 오른쪽 인덱스에있는 요소의 최대 공약수를 반환합니다. 그것이 우리의 필수 답변입니다.

암호

주어진 범위를 제외한 배열의 GCD를 찾기위한 C ++ 코드

#include<iostream>

using namespace std;
int __GCD(int a, int b)
{
    if (b == 0)
        return a;

    return __GCD(b, a % b);
}

void buildArrayOfGCD(int PreArray[], int arr[], int suffixArray[], int n)
{
    PreArray[0] = arr[0];
    for (int i=1 ; i<n; i++)
        PreArray[i] = __GCD(PreArray[i-1], arr[i]);

    suffixArray[n-1] = arr[n-1];

    for (int i=n-2; i>=0 ; i--)
        suffixArray[i] = __GCD(suffixArray[i+1], arr[i]);
}

int getGCDInRange(int l, int r, int PreArray[], int suffixArray[], int n)
{
    if (l==0)
        return suffixArray[r+1];

    if (r==n-1)
        return PreArray[l-1];
    return __GCD(PreArray[l-1], suffixArray[r+1]);
}

int main()
{
    int arr[] = {1, 3, 6, 9};
    int n = sizeof(arr)/sizeof(arr[0]);
    int PreArray[n], suffixArray[n];
    buildArrayOfGCD(PreArray, arr, suffixArray, n);

    int l = 2, r = 3;
    cout << getGCDInRange(l, r, PreArray, suffixArray, n)
         << endl;
    l = 0 ;
    r = 1;
    cout << getGCDInRange(l, r, PreArray, suffixArray, n)
         << endl;
    l = 1 ;
    r = 2;
    cout << getGCDInRange(l, r, PreArray, suffixArray, n)
         << endl;
    return 0;
}
1
3
1

주어진 범위를 제외한 배열의 GCD를 찾기위한 Java 코드

import java.util.*;

class GCDNumbers
{
    static int GCD(int a, int b)
    {
        if (b == 0)
            return a;

        return GCD(b, a % b);
    }
    
    static void buildArrayOfGCD(int preArray[],int arr[], int suffixArray[], int n)
    {
        preArray[0] = arr[0];

        for (int i = 1; i < n; i++)
            preArray[i] = GCD(preArray[i - 1], arr[i]);

        suffixArray[n - 1] = arr[n - 1];

        for (int i = n - 2; i >= 0; i--)
            suffixArray[i] = GCD(suffixArray[i + 1], arr[i]);
    }

    static int getGCDInRange(int l, int r, int preArray[], int suffixArray[], int n)
    {

        if (l == 0)
            return suffixArray[r + 1];

        if (r == n - 1)
            return preArray[l - 1];

        return GCD(preArray[l - 1], suffixArray[r + 1]);
    }
    
    public static void main(String[] args)
    {
        int arr[] = { 1, 3, 6, 9};
        int n = arr.length;
        int preArray[] = new int[n];
        int suffixArray[] = new int[n];
        buildArrayOfGCD(preArray, arr, suffixArray, n);

        int l = 2, r = 3;
        System.out.println(getGCDInRange(l, r, preArray, suffixArray, n));

        l = 0;
        r = 1;
        System.out.println(getGCDInRange
                           (l, r, preArray, suffixArray, n));

        l = 1;
        r = 2;
        System.out.println(getGCDInRange
                           (l, r, preArray, suffixArray, n));
    }
}
1
3
1

복잡성 분석

시간 복잡성

O (N + Qlogn) 어디에 "큐" 쿼리 수이며 "N”는 입력 배열의 요소 수입니다. 의 위에) preArray 및 suffixArray를 빌드하는 데 필요한 시간이 필요합니다. 그때 O (Qlog n) 각 쿼리에 대한 응답에 대해 우리는 log n을 소모하는 두 숫자의 gcd를 찾고 있기 때문에 쿼리에 응답하는 데 시간이 필요합니다. 여기서 n은 숫자이고 log는 밑이 2입니다.

공간 복잡성

주어진 범위의 요소를 제외한 모든 배열 수의 GCD에 대한 쿼리를 해결하기위한 공간 복잡성은 다음과 같습니다. 의 위에) 어디에 "엔" preArray 및 suffixArray를 저장하기위한 배열의 요소 수입니다.