ಕೊಟ್ಟಿರುವ ಸೂಚ್ಯಂಕದ ಜಿಸಿಡಿಗಳು ಒಂದು ಶ್ರೇಣಿಯಲ್ಲಿರುತ್ತವೆ


ತೊಂದರೆ ಮಟ್ಟ ಹಾರ್ಡ್
ಆಗಾಗ್ಗೆ ಕೇಳಲಾಗುತ್ತದೆ ಡಿಇ ಶಾ ಪೇಪಾಲ್ Snapchat ಸ್ನ್ಯಾಪ್ಡಿಯಲ್ ಟೈಮ್ಸ್ ಇಂಟರ್ನೆಟ್ ಕ್ಸೋಮ್
ಅರೇ ಪ್ರಶ್ನೆ ಸಮಸ್ಯೆ ವಿಭಾಗ-ಮರ ಮರ

ಸಮಸ್ಯೆ ಹೇಳಿಕೆ

'ಒಂದು ಶ್ರೇಣಿಯಲ್ಲಿನ ಸೂಚ್ಯಂಕ ಶ್ರೇಣಿಗಳ ಜಿಸಿಡಿಗಳು "ಎಂಬ ಸಮಸ್ಯೆಯು ನಿಮಗೆ ನೀಡಲಾಗಿದೆ ಎಂದು ಹೇಳುತ್ತದೆ ಪೂರ್ಣಾಂಕ ಸರಣಿ ಮತ್ತು ಕೆಲವು ಶ್ರೇಣಿಯ ಪ್ರಶ್ನೆಗಳು. ಸಮಸ್ಯೆಯ ಹೇಳಿಕೆಯು ವ್ಯಾಪ್ತಿಯಲ್ಲಿ ರೂಪುಗೊಂಡ ಉಪ-ರಚನೆಯ ಶ್ರೇಷ್ಠ ಸಾಮಾನ್ಯ ವಿಭಾಜಕವನ್ನು ಕಂಡುಹಿಡಿಯಲು ಕೇಳುತ್ತದೆ.

ಉದಾಹರಣೆ

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

ವಿವರಣೆ

ಮೊದಲ ಪ್ರಶ್ನೆಯ ಅತ್ಯಂತ ಸಾಮಾನ್ಯ ಸಾಮಾನ್ಯ ವಿಭಾಜಕವು 0 ಮತ್ತು 1 ರಿಂದ ಇರುತ್ತದೆ, ಆದ್ದರಿಂದ 10 ಮತ್ತು 5 ರ ಜಿಸಿಡಿ 5 ಆಗಿದೆ.

ಎರಡನೇ ಪ್ರಶ್ನೆಯ ಜಿಸಿಡಿ 2 ಮತ್ತು 4 ರಿಂದ ಇರುತ್ತದೆ, ಆದ್ದರಿಂದ 18, 9, 24 ರ ಜಿಸಿಡಿ 3 ಆಗಿದೆ.

ಮೊದಲ ಪ್ರಶ್ನೆಯ ಅತಿದೊಡ್ಡ ಸಾಮಾನ್ಯ ವಿಭಾಜಕವು 0 ಮತ್ತು 3 ರಿಂದ ಇರುತ್ತದೆ, ಆದ್ದರಿಂದ ಜಿಸಿಡಿ 1 ಆಗಿದೆ.

ಕೊಟ್ಟಿರುವ ಸೂಚ್ಯಂಕದ ಜಿಸಿಡಿಗಳು ಒಂದು ಶ್ರೇಣಿಯಲ್ಲಿರುತ್ತವೆ

 

ಕ್ರಮಾವಳಿ

  1. Ar [n-0] ಗೆ arr [1] ವಿಭಾಗದಿಂದ ಪ್ರಾರಂಭಿಸಿ, ಮತ್ತು ವಿಭಜನೆಯನ್ನು ಸಮಾನ ಭಾಗಗಳಾಗಿ ಮುಂದುವರಿಸಿ. ಪ್ರತಿ ಬಾರಿಯೂ ನಾವು ಪ್ರಸ್ತುತ ವಿಭಾಗವನ್ನು ಸಮಾನ ಭಾಗಗಳಾಗಿ ವಿಭಜಿಸುತ್ತೇವೆ. ನಂತರ ಪುನರಾವರ್ತಿತವಾಗಿ ಎರಡು ಭಾಗಗಳಿಗೆ ಕರೆ ಮಾಡಿ. ಮತ್ತು ಅಂತಹ ಪ್ರತಿಯೊಂದು ವಿಭಾಗಕ್ಕೂ, ನಾವು ಒಂದು ವಿಭಾಗದ ವೃಕ್ಷದಲ್ಲಿ ಸಾಮಾನ್ಯ ಸಾಮಾನ್ಯ ವಿಭಾಜಕ ಮೌಲ್ಯವನ್ನು ಸಂಗ್ರಹಿಸುತ್ತೇವೆ.
  2. ವಿಭಾಗದ ಮರವನ್ನು ನಿರ್ಮಿಸಿ ಅದು ಕೊನೆಯ ಹಂತದಿಂದ ಪಕ್ಕಕ್ಕೆ ತುಂಬುತ್ತದೆ.
  3. ವಿಭಾಗದ ಮರದ ಪ್ರತಿಯೊಂದು ನೋಡ್ ಒಂದು ನಿರ್ದಿಷ್ಟ ವ್ಯಾಪ್ತಿಗೆ ಅನುಗುಣವಾದ ಎಲ್ಲಾ ಅಂಶಗಳ ಜಿಸಿಡಿಯನ್ನು ಸಂಗ್ರಹಿಸುತ್ತದೆ.
  4. ಜಿಸಿಡಿಯ ಪ್ರಶ್ನೆಯನ್ನು ಕಂಡುಹಿಡಿಯಲು, ನೋಡ್ನ ವ್ಯಾಪ್ತಿಯು ಸ್ಟಾರ್ಟ್ ಕ್ವೆರಿ ಮತ್ತು ಎಂಡ್ ಕ್ವೆರಿಯಲ್ಲಿದ್ದರೆ, ನೋಡ್ನಲ್ಲಿ ಮೌಲ್ಯವನ್ನು ಹಿಂತಿರುಗಿಸಿ.
  5. ಇಲ್ಲದಿದ್ದರೆ, ಶ್ರೇಣಿ ಮಾನ್ಯವಾಗಿಲ್ಲ, ನಂತರ ಶೂನ್ಯ ಅಥವಾ -1 ಅನ್ನು ಹಿಂತಿರುಗಿಸಿ.
  6. ಇಲ್ಲದಿದ್ದರೆ ಜಿಸಿಡಿ ಕಾರ್ಯದ ಪುನರಾವರ್ತಿತ ಕರೆಯನ್ನು ಹಿಂತಿರುಗಿಸಿ.

ವಿವರಣೆ

ನಮಗೆ ಒಂದು ನೀಡಲಾಗಿದೆ ಪೂರ್ಣಾಂಕ ಸರಣಿ ಮತ್ತು q ಪ್ರಶ್ನೆಗಳ ಸಂಖ್ಯೆ. ಪ್ರತಿಯೊಂದು ಪ್ರಶ್ನೆಯು ಪ್ರಾರಂಭದ ಪ್ರಶ್ನೆ ಮತ್ತು ಅಂತಿಮ ಪ್ರಶ್ನೆಗಳ ವ್ಯಾಪ್ತಿಯನ್ನು ಹೊಂದಿರುತ್ತದೆ. ಈ ವ್ಯಾಪ್ತಿಯಲ್ಲಿ, ನಿರ್ದಿಷ್ಟ ಶ್ರೇಣಿಯನ್ನು ಪೂರೈಸುವ ಎಲ್ಲ ಸಂಖ್ಯೆಗಳ ಸಾಮಾನ್ಯ ಸಾಮಾನ್ಯ ವಿಭಾಜಕವನ್ನು ನಾವು ಕಂಡುಹಿಡಿಯಬೇಕಾಗಿದೆ. ಇದಕ್ಕಾಗಿ ನಾವು ನಿರ್ಮಿಸಲಿದ್ದೇವೆ ವಿಭಾಗದಲ್ಲಿ ಮರ, ನಾವು ಲಾಗ್ ಎನ್ * ಲಾಗ್ ಎನ್ ನ ಸಮರ್ಥ ಸಮಯದಲ್ಲಿ ಪ್ರಶ್ನೆಗಳನ್ನು ಪರಿಹರಿಸುತ್ತೇವೆ.

ನಾವು ರಚನೆಯ ಮರವನ್ನು ರಚನೆಯ 0 ನೇ ಸ್ಥಾನದಿಂದ ರಚನೆಯ ಕೊನೆಯ ಸ್ಥಾನಕ್ಕೆ ನಿರ್ಮಿಸಲು ಪ್ರಾರಂಭಿಸುತ್ತೇವೆ ಮತ್ತು ಪ್ರಮುಖ ಭಾಗವು ರಚನೆಯನ್ನು ಎರಡು ಭಾಗಗಳಾಗಿ ವಿಂಗಡಿಸುತ್ತದೆ. ರಚನೆಯ ಉದ್ದವು ಒಂದಾಗುವವರೆಗೆ ನಾವು ಅದನ್ನು ವಿಭಜಿಸುವುದನ್ನು ಮುಂದುವರಿಸುತ್ತೇವೆ, ನಂತರ ಮುಂದಿನ ಹಂತದಲ್ಲಿ ಕಾರ್ಯವನ್ನು ಪುನರಾವರ್ತಿತವಾಗಿ ರಚನೆಯ ಎರಡೂ ಭಾಗಗಳಿಗೆ ಕರೆಯುತ್ತೇವೆ. ಇಲ್ಲಿ ನಾವು ಮರದ ನೋಡ್ನಲ್ಲಿ ಅತ್ಯಂತ ಸಾಮಾನ್ಯವಾದ ವಿಭಾಜಕವನ್ನು ಸಂಗ್ರಹಿಸುತ್ತೇವೆ. ಎಲೆ ನೋಡ್‌ಗಳನ್ನು ಹೊರತುಪಡಿಸಿ ಎಲ್ಲಾ ಆಂತರಿಕ ನೋಡ್‌ಗಳು ಶೂನ್ಯವಾಗಿರುವುದಿಲ್ಲ. ಹಾಗೆ ರೂಪುಗೊಂಡ ಮರವು ಬೈನರಿ ಮರವಾಗಿರುತ್ತದೆ. ಏಕೆಂದರೆ ಪ್ರತಿ ನೋಡ್ ಮಟ್ಟದಲ್ಲಿ ರಚನೆಯ ಎರಡು ಭಾಗಗಳಿವೆ. ಆದರೆ ಬೈನರಿ ಮರಕ್ಕೆ ಹೋಲಿಸಿದರೆ, ಅಲ್ಲಿ ನೋಡ್‌ಗಳು ಒಂದೇ ಸಂಖ್ಯೆಯ ಬದಲು ಶ್ರೇಣಿಯನ್ನು ಪ್ರತಿನಿಧಿಸುತ್ತವೆ.

ನೀಡಲಾದ ಗ್ರೇಟೆಸ್ಟ್ ಕಾಮನ್ ಡಿವೈಸರ್ನ ಪ್ರತಿ ಪ್ರಶ್ನೆಗೆ, ನೋಡ್ನ ವ್ಯಾಪ್ತಿಯು ಸ್ಟಾರ್ಟ್ ಕ್ವೆರಿ ಮತ್ತು ಎಂಡ್ ಕ್ವೆರಿ ವ್ಯಾಪ್ತಿಯಲ್ಲಿದೆ ಎಂದು ನಾವು ಪರಿಶೀಲಿಸುತ್ತೇವೆ. ನಂತರ ನಾವು ಸೆಗ್ಮೆಂಟ್ ಟ್ರೀನ ನೋಡ್ನಲ್ಲಿ ಮೌಲ್ಯವನ್ನು ಹಿಂತಿರುಗಿಸುತ್ತೇವೆ. ನಾವು ಎರಡನೇ ಷರತ್ತನ್ನು ಹೊಂದಿದ್ದೇವೆ, ಅಲ್ಲಿ ನೋಡ್ನ ವ್ಯಾಪ್ತಿಯು ಪ್ರಾರಂಭದ ಪ್ರಶ್ನೆ ಶ್ರೇಣಿ ಮತ್ತು ಎಂಡ್‌ಕ್ವೆರಿ ಶ್ರೇಣಿಯಿಂದ ಹೊರಗಿದ್ದರೆ. ನಂತರ ನಾವು -1 ಅಥವಾ ಶೂನ್ಯ ಮೌಲ್ಯವನ್ನು ಹಿಂತಿರುಗಿಸುತ್ತೇವೆ. ಮತ್ತು ಕಾರ್ಯವನ್ನು ನಿರಂತರವಾಗಿ ಪ್ರಗತಿಪರವಾಗಿಸಲು, ನಾವು ನೋಡ್‌ನ ಮಗುವನ್ನು ಎಡ ಮತ್ತು ಬಲಕ್ಕೆ ಪುನರಾವರ್ತಿತವಾಗಿ ಕರೆಯುತ್ತೇವೆ. ನಂತರ ನೋಡ್‌ಗಳಿಂದ ಹಿಂತಿರುಗಿದ ಮೌಲ್ಯದ ಸಾಮಾನ್ಯ ಸಾಮಾನ್ಯ ವಿಭಾಜಕವನ್ನು ಕಂಡುಹಿಡಿಯಿರಿ.

ಕೋಡ್

ಒಂದು ಶ್ರೇಣಿಯಲ್ಲಿ ನಿರ್ದಿಷ್ಟ ಸೂಚ್ಯಂಕ ಶ್ರೇಣಿಗಳ ಜಿಸಿಡಿಗಳನ್ನು ಕಂಡುಹಿಡಿಯಲು ಸಿ ++ ಕೋಡ್

#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

ಒಂದು ಶ್ರೇಣಿಯಲ್ಲಿ ನೀಡಿರುವ ಸೂಚ್ಯಂಕ ಶ್ರೇಣಿಗಳ ಜಿಸಿಡಿಗಳನ್ನು ಹುಡುಕಲು ಜಾವಾ ಕೋಡ್

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))) ಅಲ್ಲಿ “ಎನ್” ಇದು ನೋಡ್ಗಳ ಸಂಖ್ಯೆ ಮತ್ತು "ಎ" ಮತ್ತು “ಬಿ” ವಿಲೀನ ಕಾರ್ಯಾಚರಣೆಯ ಸಮಯದಲ್ಲಿ ಜಿಸಿಡಿಯನ್ನು ಲೆಕ್ಕಹಾಕುವ ನೋಡ್‌ಗಳು. ಒ (ಎನ್ ಲಾಗ್ನ್) ನಿರ್ಮಾಣಕ್ಕಾಗಿ ಸಮಯವನ್ನು ಕಳೆಯಲಾಗುತ್ತದೆ ಮತ್ತು ಒ (ಲಾಗ್ ಎನ್) ಪ್ರತಿ ಪ್ರಶ್ನೆಗೆ ಉತ್ತರಿಸಲು ಮತ್ತು ನಂತರ ಒ (ಲಾಗ್ (ನಿಮಿಷ (ಎ, ಬಿ))) ಜಿಸಿಡಿ ಹುಡುಕುವ ಸಮಯ.

ಬಾಹ್ಯಾಕಾಶ ಸಂಕೀರ್ಣತೆ

ಓ (ಎನ್) ಅಲ್ಲಿ “ಎನ್” ನೋಡ್ಗಳು. ವಿಭಾಗದ ಮರದ ನಿರ್ಮಾಣದಲ್ಲಿ ಜಾಗವನ್ನು ಖರ್ಚು ಮಾಡಲಾಗುತ್ತದೆ.