ನಿರ್ದಿಷ್ಟ ಶ್ರೇಣಿಯಲ್ಲಿನ ಅಂಶಗಳನ್ನು ಹೊರತುಪಡಿಸಿ ರಚನೆಯ ಎಲ್ಲಾ ಸಂಖ್ಯೆಗಳ ಜಿಸಿಡಿಗಾಗಿ ಪ್ರಶ್ನೆಗಳು


ತೊಂದರೆ ಮಟ್ಟ ಹಾರ್ಡ್
ಆಗಾಗ್ಗೆ ಕೇಳಲಾಗುತ್ತದೆ ಅಮೆಜಾನ್ ಕ್ಯಾಪಿಟಲ್ ಒನ್ ಡಿಇ ಶಾ ಗೂಗಲ್ ಪೇಪಾಲ್ ಕೊರಾ ಟೆರಾಡಾಟಾ
ಅರೇ ಡೈನಾಮಿಕ್ ಪ್ರೊಗ್ರಾಮಿಂಗ್ ಜಿಸಿಡಿ ಮಠ ಪ್ರಶ್ನೆ ಸಮಸ್ಯೆ

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

“ನಿರ್ದಿಷ್ಟ ಶ್ರೇಣಿಯಲ್ಲಿನ ಅಂಶಗಳನ್ನು ಹೊರತುಪಡಿಸಿ ರಚನೆಯ ಎಲ್ಲಾ ಸಂಖ್ಯೆಗಳ ಜಿಸಿಡಿಗಾಗಿ ಪ್ರಶ್ನೆಗಳು” ಸಮಸ್ಯೆ ನಿಮಗೆ ನೀಡಲಾಗುವುದು ಎಂದು ಹೇಳುತ್ತದೆ ಪೂರ್ಣಾಂಕ ಸರಣಿ ಮತ್ತು q ಪ್ರಶ್ನೆಗಳ ಸಂಖ್ಯೆ. ಪ್ರತಿಯೊಂದು ಪ್ರಶ್ನೆಯು ಎಡ ಮತ್ತು ಬಲ ಸಂಖ್ಯೆಯನ್ನು ಹೊಂದಿರುತ್ತದೆ. ಸಮಸ್ಯೆಯ ಹೇಳಿಕೆಯು ಪ್ರಶ್ನೆಯ ನಿರ್ದಿಷ್ಟ ವ್ಯಾಪ್ತಿಯಲ್ಲಿ ಹೊರತುಪಡಿಸಿ ಎಲ್ಲಾ ಪೂರ್ಣಾಂಕಗಳ ಸಾಮಾನ್ಯ ಸಾಮಾನ್ಯ ವಿಭಾಜಕವನ್ನು ಕಂಡುಹಿಡಿಯಲು ಕೇಳುತ್ತದೆ.

ಉದಾಹರಣೆ

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

ವಿವರಣೆ

ಸೂಚ್ಯಂಕ 2 ರಿಂದ 3 ರವರೆಗಿನ ಅಂಶಗಳನ್ನು ಹೊರತುಪಡಿಸಿ ಅಂಶಗಳ ಜಿಸಿಡಿ, ಅಂದರೆ 1 ಮತ್ತು 3 ರ ಜಿಸಿಡಿ 1 ಆಗಿದೆ

ಈಗ ಸೂಚ್ಯಂಕ 0 ರಿಂದ 1 ರವರೆಗಿನ ಅಂಶಗಳನ್ನು ಹೊರತುಪಡಿಸಿ ಅಂಶಗಳ ಜಿಸಿಡಿ, ಅಂದರೆ 6 ಮತ್ತು 9 ರ ಜಿಸಿಡಿ 3 ಆಗಿದೆ

ಮತ್ತೆ ಸೂಚ್ಯಂಕ 1 ರಿಂದ 2 ರವರೆಗಿನ ಅಂಶಗಳನ್ನು ಹೊರತುಪಡಿಸಿ ಅಂಶಗಳ ಜಿಸಿಡಿ, ಅಂದರೆ 1 ಮತ್ತು 9 ರ ಜಿಸಿಡಿ 1 ಆಗಿದೆ

ನಿರ್ದಿಷ್ಟ ಶ್ರೇಣಿಯಲ್ಲಿನ ಅಂಶಗಳನ್ನು ಹೊರತುಪಡಿಸಿ ರಚನೆಯ ಎಲ್ಲಾ ಸಂಖ್ಯೆಗಳ ಜಿಸಿಡಿಗಾಗಿ ಪ್ರಶ್ನೆಗಳು

 

ಕ್ರಮಾವಳಿ

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

ವಿವರಣೆ

ಉತ್ತರಿಸಲು ಪೂರ್ಣಾಂಕಗಳು ಮತ್ತು ಪ್ರಶ್ನೆಗಳ ಒಂದು ಶ್ರೇಣಿಯನ್ನು ನೀಡಲಾಗಿದೆ. ಕಂಡುಹಿಡಿಯಲು ನಮ್ಮನ್ನು ಕೇಳಲಾಗುತ್ತದೆ ಶ್ರೇಷ್ಠ ಸಾಮಾನ್ಯ ವಿಭಾಜಕ ಪ್ರಶ್ನೆಯ ನಿರ್ದಿಷ್ಟ ಶ್ರೇಣಿಯಲ್ಲಿನ ಎಲ್ಲಾ ಪೂರ್ಣಾಂಕಗಳನ್ನು ಹೊರತುಪಡಿಸಿ ಸಂಖ್ಯೆಗಳ. 0 ರ ಶ್ರೇಣಿಯಲ್ಲಿ ನಮಗೆ 1 ರಿಂದ 5 ರ ವ್ಯಾಪ್ತಿಯನ್ನು ನೀಡಿದರೆ. ಇದರರ್ಥ ನಾವು ಒಂದು ಶ್ರೇಣಿಯಲ್ಲಿ ಆರ್ [0] ಮತ್ತು ಅರ್ [1] ಹೊರತುಪಡಿಸಿ ಎಲ್ಲಾ ಪೂರ್ಣಾಂಕಗಳ ಶ್ರೇಷ್ಠ ಸಾಮಾನ್ಯ ವಿಭಾಜಕವನ್ನು ಕಂಡುಹಿಡಿಯಬೇಕು. ಎಡ ಮತ್ತು ಬಲವನ್ನು ಶ್ರೇಣಿಯಾಗಿ ಒಳಗೊಂಡಿರುವ ಪ್ರಶ್ನೆಯನ್ನು ನೀಡಲಾಗಿದೆ. ಈ ವ್ಯಾಪ್ತಿಯಲ್ಲಿ ಬರುವ ಪೂರ್ಣಾಂಕಗಳನ್ನು ನಾವು ಬಿಡಬೇಕಾಗಿದೆ.

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

ಕೊಟ್ಟಿರುವ ಶ್ರೇಣಿಯ ಪ್ರತಿ ಪ್ರಶ್ನೆಗೆ, ಕೊಟ್ಟಿರುವ ಎಡ ಶ್ರೇಣಿ 0 ಕ್ಕೆ ಸಮನಾಗಿದೆಯೇ ಎಂದು ಪರಿಶೀಲಿಸಿ. ಹೀಗೆ ಅರೇ [ಬಲ + 1] ಪ್ರತ್ಯಯದ ಮೌಲ್ಯವನ್ನು ಹಿಂತಿರುಗಿಸಿ. ಬಲದ ಮೌಲ್ಯವು ರಚನೆಯ ಉದ್ದಕ್ಕೆ ಸಮನಾಗಿದೆಯೇ ಎಂದು ಪರಿಶೀಲಿಸಿ. ನಂತರ ಪ್ರಿಅರ್ರೆ [ಎಡ -1] ಮೌಲ್ಯವನ್ನು ಹಿಂತಿರುಗಿಸಿ. ಪ್ರಿಅರೇನಲ್ಲಿ ಎಡ ಸೂಚ್ಯಂಕದಲ್ಲಿರುವ ಅಂಶದ ಅತ್ಯಂತ ಸಾಮಾನ್ಯ ಸಾಮಾನ್ಯ ವಿಭಾಜಕವನ್ನು ಮತ್ತು ಪ್ರತ್ಯಯ ಅರೇನಲ್ಲಿ ಬಲ ಸೂಚ್ಯಂಕದಲ್ಲಿ ಅಂಶವನ್ನು ಹಿಂದಿರುಗಿಸಿ. ಅದು ನಮ್ಮ ಅಗತ್ಯ ಉತ್ತರವಾಗಿರುತ್ತದೆ.

ಕೋಡ್

ನಿರ್ದಿಷ್ಟ ಶ್ರೇಣಿಯನ್ನು ಹೊರತುಪಡಿಸಿ ರಚನೆಯ ಜಿಸಿಡಿ ಹುಡುಕಲು ಸಿ ++ ಕೋಡ್

#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

ನಿರ್ದಿಷ್ಟ ಶ್ರೇಣಿಯನ್ನು ಹೊರತುಪಡಿಸಿ ರಚನೆಯ ಜಿಸಿಡಿ ಹುಡುಕಲು ಜಾವಾ ಕೋಡ್

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

ಸಂಕೀರ್ಣತೆ ವಿಶ್ಲೇಷಣೆ

ಸಮಯ ಸಂಕೀರ್ಣತೆ

ಒ (ಎನ್ + ಕ್ಲಾಗ್ನ್) ಅಲ್ಲಿ "ಪ್ರಶ್ನೆ" ಪ್ರಶ್ನೆಗಳ ಸಂಖ್ಯೆ ಮತ್ತು “N”ಎಂಬುದು ಇನ್ಪುಟ್ ಅರೇನಲ್ಲಿನ ಅಂಶಗಳ ಸಂಖ್ಯೆ. ಒ (ಎನ್) ಪ್ರಿಅರ್ರೆ ಮತ್ತು ಪ್ರತ್ಯಯ ಅರೇ ನಿರ್ಮಾಣಕ್ಕೆ ಸಮಯ ಬೇಕಾಗುತ್ತದೆ. ನಂತರ ಒ (ಕ್ಲಾಗ್ ಎನ್) ಪ್ರಶ್ನೆಗಳಿಗೆ ಉತ್ತರಿಸಲು ಸಮಯ ಬೇಕಾಗುತ್ತದೆ ಏಕೆಂದರೆ ಪ್ರತಿ ಪ್ರಶ್ನೆಗೆ ಉತ್ತರಿಸಲು ನಾವು ಎರಡು ಸಂಖ್ಯೆಗಳ ಜಿಸಿಡಿಯನ್ನು ಹುಡುಕುತ್ತಿದ್ದೇವೆ ಅದು ನಮಗೆ ಲಾಗ್ n ವೆಚ್ಚವಾಗುತ್ತದೆ, ಅಲ್ಲಿ n ಸಂಖ್ಯೆ ಮತ್ತು ಲಾಗ್ ಬೇಸ್ 2 ರೊಂದಿಗೆ ಇರುತ್ತದೆ.

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

ನಿರ್ದಿಷ್ಟ ಶ್ರೇಣಿಯಲ್ಲಿನ ಅಂಶಗಳನ್ನು ಹೊರತುಪಡಿಸಿ ಎಲ್ಲಾ ಶ್ರೇಣಿಯ ಜಿಸಿಡಿಯ ಪ್ರಶ್ನೆಗಳನ್ನು ಪರಿಹರಿಸುವ ಸ್ಥಳ ಸಂಕೀರ್ಣತೆ ಒ (ಎನ್) ಅಲ್ಲಿ “ಎನ್” ಪೂರ್ವಅರೇ ಮತ್ತು ಪ್ರತ್ಯಯ ಅರೇ ಅನ್ನು ಸಂಗ್ರಹಿಸಲು ರಚನೆಯ ಅಂಶಗಳ ಸಂಖ್ಯೆ.