배열에서 주어진 인덱스 범위의 GCD


난이도 하드
자주 묻는 질문 DE Shaw 페이팔 Snapchat 스냅 딜 타임즈 인터넷 Xome
배열 쿼리 문제 세그먼트 트리 나무

문제 정책

'배열에서 지정된 인덱스 범위의 GCD'문제는 정수 정렬 및 일부 범위 쿼리. 문제 설명은 범위 내에서 이렇게 형성된 하위 배열의 최대 공약수를 찾아야합니다.

arr[] = {10, 5, 18, 9, 24}
Query: {(0, 1), (2, 4), (0, 3)}
5 3 1

설명

첫 번째 쿼리의 최대 공약수 범위는 0과 1이므로 GCD 10과 5는 5입니다.

두 번째 쿼리의 GCD 범위는 2와 4이므로 18, 9, 24의 GCD는 3입니다.

첫 번째 쿼리의 최대 공약수 범위는 0과 3이므로 GCD는 1입니다.

배열에서 주어진 인덱스 범위의 GCD

 

암호알고리즘

  1. arr [0]에서 arr [n-1]까지 섹션으로 시작하고 동일한 부분으로 계속 분할합니다. 매번 현재 섹션을 동일한 부분으로 분할합니다. 그런 다음 두 부분을 재귀 적으로 호출합니다. 그리고 이러한 각 세그먼트에 대해 세그먼트 트리에 최대 공약수 값을 저장합니다.
  2. 마지막 레벨을 제외하고 채울 세그먼트 트리를 만듭니다.
  3. 세그먼트 트리의 각 노드는 특정 범위에 해당하는 모든 요소의 GCD를 저장합니다.
  4. GCD의 쿼리를 찾기 위해 노드의 범위가 startQuery 및 endQuery에 있으면 node의 값을 반환합니다.
  5. 그렇지 않으면 범위가 유효하지 않으면 null 또는 -1을 반환합니다.
  6. 그렇지 않으면 GCD 함수의 재귀 호출을 반환합니다.

설명

우리는 주어진 정수 정렬 및 q 쿼리 수. 각 쿼리에는 범위가 startQuery 및 endQuery로 포함됩니다. 이 범위 내에서 주어진 범위를 만족하는 모든 숫자의 최대 공약수를 찾아야합니다. 이를 위해 우리는 분절 로그 N * log n의 효율적인 시간에 쿼리를 해결합니다.

배열의 0 번째 위치에서 배열의 마지막 위치까지 세그먼트 트리를 만들기 시작합니다. 중요한 부분은 배열을 두 부분으로 나누는 것입니다. 배열의 길이가 XNUMX이 될 때까지 계속 나눈 다음 다음 단계에서 배열의 두 부분에 대해 함수를 재귀 적으로 호출합니다. 여기서 우리는 트리의 노드에 최대 공약수를 저장합니다. 리프 노드를 제외하고 모든 내부 노드는 null이 아닙니다. 이렇게 형성된 트리는 이진 트리가됩니다. 모든 노드 수준에서 어레이의 두 부분이 있기 때문입니다. 그러나 노드가 단일 숫자 대신 범위를 나타내는 이진 트리와 비교됩니다.

주어진 최대 공약수의 각 쿼리에 대해 노드의 범위가 startQuery 및 endQuery 범위 내에 있는지 확인합니다. 그런 다음 세그먼트 트리의 노드에 값을 반환합니다. 또한 노드의 범위가 startQuery 범위 및 endQuery 범위를 벗어난 경우 두 번째 조건이 있습니다. 그런 다음 -1 또는 null 값을 반환합니다. 그리고 함수를 지속적으로 점진적으로 만들기 위해 노드의 자식을 왼쪽과 오른쪽 모두 재귀 적으로 호출합니다. 그런 다음 노드에서 반환 된 값의 최대 공약수를 찾습니다.

암호

배열에서 주어진 인덱스 범위의 GCD를 찾는 C ++ 코드

#include<iostream>
#include<math.h>

using namespace std;

int *segTree;

int gcd(int a, int b)
{
    if (a < b)
    {
        int temp = b;
        b = a;
        a = temp;
    }

    if (b==0)
        return a;
    return gcd(b,a%b);
}

int getGCDOfNumber(int startNode, int endNode, int startQuery, int endQuery, int si)
{
    if (startNode>endQuery || endNode < startQuery)
        return 0;
    if (startQuery<=startNode && endQuery>=endNode)
        return segTree[si];

    int mid = startNode+(endNode-startNode)/2;

    return gcd(getGCDOfNumber(startNode, mid, startQuery, endQuery, si*2+1),
               getGCDOfNumber(mid+1, endNode, startQuery, endQuery, si*2+2));
}

int findRangeGcd(int startNode, int endNode, int arr[],int n)
{
    if (startNode<0 || endNode > n-1 || startNode>endNode)
    {
        cout << "Invalid Arguments" << "\n";
        return -1;
    }
    return getGCDOfNumber(0, n-1, startNode, endNode, 0);
}

int buildSegementTree(int arr[], int startNode, int endNode, int si)
{
    if (startNode==endNode)
    {
        segTree[si] = arr[startNode];
        return segTree[si];
    }
    int mid = startNode+(endNode-startNode)/2;

    segTree[si] = gcd(buildSegementTree(arr, startNode, mid, si*2+1),
                      buildSegementTree(arr, mid+1, endNode, si*2+2));
    return segTree[si];
}

int *constructendNodegmentTree(int arr[], int n)
{
    int height = (int)(ceil(log2(n)));
    int size = 2*(int)pow(2, height)-1;
    segTree = new int[size];
    buildSegementTree(arr, 0, n-1, 0);
    return segTree;
}

int main()
{
    int a[] = {10, 5, 18, 9, 24};
    int n = sizeof(a)/sizeof(a[0]);

    constructendNodegmentTree(a, n);

    int l = 0, r = 1;
    cout << "Greatest Common Divisor is: ";
    cout << findRangeGcd(l, r, a, n) << "\n";

    l = 2;
    r = 4;
    cout << "Greatest Common Divisor is: ";
    cout << findRangeGcd(l, r, a, n) << "\n";

    l = 0;
    r = 3;
    cout << "Greatest Common Divisor is: ";
    cout << findRangeGcd(l, r, a, n) << "\n";

    return 0;
}
Greatest Common Divisor is: 5
Greatest Common Divisor is: 3
Greatest Common Divisor is: 1

배열에서 주어진 인덱스 범위의 GCD를 찾는 Java 코드

import java.io.*;

public class GCDOfNumber
{
    private static int[] segTree;

    public static int[] buildSegmentTree(int[] arr)
    {
        int height = (int)Math.ceil(Math.log(arr.length)/Math.log(2));
        int size = 2*(int)Math.pow(2, height)-1;
        segTree = new int[size];
        SegementTree(arr, 0, arr.length-1, 0);

        return segTree;
    }

    public static int SegementTree(int[] arr, int startNode,
                                   int endNode, int si)
    {
        if (startNode==endNode)
        {
            segTree[si] = arr[startNode];

            return segTree[si];
        }
        int mid = startNode+(endNode-startNode)/2;

        segTree[si] = gcd(SegementTree(arr, startNode, mid, si*2+1),
                          SegementTree(arr, mid+1, endNode, si*2+2));
        return segTree[si];
    }

    private static int gcd(int a, int b)
    {
        if (a < b)
        {
            int temp = b;
            b = a;
            a = temp;
        }

        if (b==0)
            return a;
        return gcd(b,a%b);
    }

    public static int findRangeGcd(int startNode, int endNode, int[] arr)
    {
        int n = arr.length;

        if (startNode<0 || endNode > n-1 || startNode>endNode)
            throw new IllegalArgumentException("Invalid arguments");

        return findGcd(0, n-1, startNode, endNode, 0);
    }

    public static int findGcd(int startNode, int endNode, int startQuery, int endQuery, int si)
    {
        if (startNode>endQuery || endNode < startQuery)
            return 0;

        if (startQuery<=startNode && endQuery>=endNode)
            return segTree[si];

        int mid = startNode+(endNode-startNode)/2;

        return gcd(findGcd(startNode, mid, startQuery, endQuery, si*2+1),
                   findGcd(mid+1, endNode, startQuery, endQuery, si*2+2));
    }

    public static void main(String[] args)throws IOException
    {
        int[] a = {10, 5, 18, 9, 24};

        buildSegmentTree(a);

        int l = 0, r = 1;
        System.out.println("Greatest Common Divisor is: "+findRangeGcd(l, r, a));

        l = 2;
        r = 4;
        System.out.println("Greatest Common Divisor is: "+findRangeGcd(l, r, a));

        l = 0;
        r = 3;
        System.out.println("Greatest Common Divisor is: "+findRangeGcd(l, r, a));
    }
}
Greatest Common Divisor is: 5
Greatest Common Divisor is: 3
Greatest Common Divisor is: 1

복잡성 분석

시간 복잡성

O (n log n + log n * log (min (a, b))) 어디에 "엔" 노드의 수이며 "A""비" 병합 작업 중에 GCD가 계산되는 노드입니다. O (n logn) 건설에 소요되는 시간과 O (로그 n) 각 질문에 답한 다음 O (로그 (분 (a, b))) gcd를 찾는 시간.

공간 복잡성

O (N) 어디에 "엔" 노드입니다. 공간은 세그먼트 트리의 구성에 사용됩니다.