ಶ್ರೇಣಿ LCM ಪ್ರಶ್ನೆಗಳು


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

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

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

ಉದಾಹರಣೆ

arr[] = {2, 4, 6, 9, 10, 8, 7, 5, 14, 1};
Query: {(2, 5), (3, 7), (5, 8)}
360 2520 280

ವಿವರಣೆ

(2,5) 6,9,10 ಮತ್ತು 8 ರ ಎಲ್ಸಿಎಂ 360 ಆಗಿದೆ

ಈಗ ಮತ್ತೆ ಮುಂದಿನ ಪ್ರಶ್ನೆಗೆ, (3,7), 9,10,8,7 ಮತ್ತು 5 ರ ಎಲ್ಸಿಎಂ 2520 ಆಗಿದೆ

ಮತ್ತು ಕೊನೆಗೆ (5,8) 8,7,5 ಮತ್ತು 14 ರ ಎಲ್ಸಿಎಂ 280 ಆಗಿರುತ್ತದೆ

ಶ್ರೇಣಿ LCM ಪ್ರಶ್ನೆಗಳು

 

ಕ್ರಮಾವಳಿ

  1. ಎರಡು ಘೋಷಿಸಿ ಸರಣಿಗಳು.
  2. ನಿರ್ಮಿಸಿ ವಿಭಾಗ ಮರ ಎಡ ಮಗು ಮತ್ತು ಬಲ ಮಗುವಿಗೆ ಕಾರ್ಯಗಳನ್ನು ಪುನರಾವರ್ತಿತವಾಗಿ ಕರೆಯುವ ಮೂಲಕ.
  3. ಎಡ ಮಕ್ಕಳ ನೋಡ್ ಮತ್ತು ಬಲ ಮಕ್ಕಳ ನೋಡ್ಗಾಗಿ ಎಲ್ಸಿಎಂ ಪಡೆಯಿರಿ.
  4. ಒಂದು ಸಂಖ್ಯೆಯ ಎಲ್ಸಿಎಂ ಪಡೆಯಲು, ಎಡ ಮಗು ಮತ್ತು ಬಲ ಮಗುವಿನ ಉತ್ಪನ್ನವನ್ನು ಅವರ ಜಿಸಿಡಿಯಿಂದ ಭಾಗಿಸಿ.
  5. ಪ್ರತಿ ಪ್ರಶ್ನೆಗೆ ಎಡ ಮತ್ತು ಬಲಕ್ಕೆ, ಶ್ರೇಣಿ ಮಾನ್ಯವಾಗಿಲ್ಲವೇ ಎಂದು ಪರಿಶೀಲಿಸಿ ನಂತರ 1 ಹಿಂತಿರುಗಿ, ಇಲ್ಲದಿದ್ದರೆ ಎಡವು ನೋಡ್‌ನ ಆರಂಭಿಕ ಮೌಲ್ಯಕ್ಕಿಂತ ಕಡಿಮೆಯಿದೆಯೇ ಮತ್ತು ಬಲವು ಅಂತ್ಯಗೊಳ್ಳುವ ನೋಡ್‌ನ ಮೌಲ್ಯಕ್ಕಿಂತ ದೊಡ್ಡದಾಗಿದೆ ಎಂದು ಪರಿಶೀಲಿಸಿ, ನಂತರ ಹಿಂತಿರುಗಿ ಮರದ ಪ್ರಸ್ತುತ ಮೌಲ್ಯ ನೋಡ್.
  6. ಮೇಲಿನ ಯಾವುದೇ ಷರತ್ತುಗಳು ನಿಜವಾಗದಿದ್ದರೆ, ಎಡ ನೋಡ್ ಎಲ್ಸಿಎಂ ಮತ್ತು ಬಲ ನೋಡ್ ಎಲ್ಸಿಎಂ ಪಡೆಯಲು ಪುನರಾವರ್ತಿತವಾಗಿ ಕಾರ್ಯವನ್ನು ಕರೆ ಮಾಡಿ ಮತ್ತು ನಂತರ ಈ ಸಂಖ್ಯೆಗಳ ಎಲ್ಸಿಎಂ ಪಡೆಯಲು ಎಲ್ಸಿಎಂ ಕಾರ್ಯವನ್ನು ಕರೆ ಮಾಡಿ.

ವಿವರಣೆ

ಪೂರ್ಣಾಂಕ ರಚನೆ ಮತ್ತು ಎಡ ಮತ್ತು ಬಲ ವ್ಯಾಪ್ತಿಯೊಂದಿಗೆ ಕೆಲವು ಪ್ರಶ್ನೆಗಳನ್ನು ನೀಡಲಾಗಿದೆ. ಕಂಡುಹಿಡಿಯಿರಿ LCM ವ್ಯಾಪ್ತಿಯಲ್ಲಿರುವ ಎಲ್ಲಾ ಸಂಖ್ಯೆಗಳನ್ನು ಒಳಗೊಂಡಂತೆ. ಎಲ್ಸಿಎಂ ಸೂತ್ರವನ್ನು ಆರ್ಸಿ [ಎಡ, ಎಡ + 1, ……., ಬಲ -1, ಬಲ] ನ ಎಲ್ಸಿಎಂ ಆಗಿ ಕಾರ್ಯಗತಗೊಳಿಸುತ್ತದೆ ಎಂದು ಕಂಡುಹಿಡಿಯಲು, ಆದರೆ ಇದರಲ್ಲಿ, ನಾವು ಮರವನ್ನು ಬಳಸುತ್ತೇವೆ. ನಾವು ಒಂದು ವಿಭಾಗದ ಮರವನ್ನು ನಿರ್ಮಿಸಲಿದ್ದೇವೆ. ಒಂದು ಶ್ರೇಣಿಯಲ್ಲಿ ಕೇವಲ ಒಂದು ಮೌಲ್ಯವಿದೆಯೇ ಎಂದು ನಾವು ಪರಿಶೀಲಿಸುತ್ತೇವೆ, ನಂತರ ಆ ನಿರ್ದಿಷ್ಟ ಮೌಲ್ಯವನ್ನು ಮರದ ನೋಡ್‌ನಲ್ಲಿ ಸೇರಿಸಿ. ಬೇರೆ, ನಾವು ಶ್ರೇಣಿಯನ್ನು ಅರ್ಧದಷ್ಟು ವಿಭಜಿಸಿ ಮರವನ್ನು ನಿರ್ಮಿಸಲು ಪ್ರಾರಂಭಿಸುತ್ತೇವೆ, ಎಡ ಮಕ್ಕಳ ನೋಡ್‌ಗಾಗಿ. ನಂತರ ಮೌಲ್ಯಗಳನ್ನು ಎಡ ನೋಡ್‌ಗೆ 2 * ನೋಡ್‌ನಂತೆ ಮತ್ತು ಬಲ ಚೈಲ್ಡ್ ನೋಡ್‌ಗೆ 2 * ನೋಡ್ + 1 ಅನ್ನು ರವಾನಿಸಿ ಮತ್ತು ಈ ಮೌಲ್ಯದ ಎಲ್‌ಸಿಎಂ ಅನ್ನು ಗೆಟ್‌ಎಲ್‌ಸಿಎಂ ಕಾರ್ಯಕ್ಕೆ ರವಾನಿಸುವ ಮೂಲಕ ಪಡೆಯಿರಿ. ಮತ್ತು ಈ ಎರಡು ಮಕ್ಕಳ ನೋಡ್‌ಗಳ LCM ಅನ್ನು ಪಡೆಯಿರಿ ಮತ್ತು ಮರದ ನೋಡ್ ಸ್ಥಾನದಲ್ಲಿ ಮೌಲ್ಯವನ್ನು ಹಿಂದಿರುಗಿಸಿದ ಅಂಗಡಿಯನ್ನು ಪಡೆಯಿರಿ.

ಎಲ್ಸಿಎಂ ಕಾರ್ಯದಲ್ಲಿ, ನಾವು ಆ ಎಡ ಮತ್ತು ಬಲ ನೋಡ್ ಮೌಲ್ಯಗಳ ಸಾಮಾನ್ಯ ಸಾಮಾನ್ಯ ವಿಭಾಜಕವನ್ನು ಕಂಡುಹಿಡಿಯಲಿದ್ದೇವೆ. ನಂತರ ನಾವು ಎಡ ಮತ್ತು ಬಲ ನೋಡ್ಗಳ ಉತ್ಪನ್ನದ ವಿಭಜನೆಯ ಉತ್ಪನ್ನವನ್ನು ಮತ್ತು ಎಡ ಮತ್ತು ಬಲ ನೋಡ್ನ ಸಾಮಾನ್ಯ ಸಾಮಾನ್ಯ ವಿಭಾಜಕವನ್ನು ಹಿಂದಿರುಗಿಸುತ್ತೇವೆ.

ಪ್ರತಿ ಪ್ರಶ್ನೆಗೆ ನಾವು ಎಡ ಮತ್ತು ಬಲ ಸ್ಥಾನವಾಗಿ ಪಡೆಯುತ್ತೇವೆ, ಅಂತಿಮ ಮೌಲ್ಯವು ಎಡಕ್ಕಿಂತ ಕಡಿಮೆಯಿದ್ದರೆ ಅಥವಾ ಪ್ರಾರಂಭದ ಮೌಲ್ಯವು ಬಲಕ್ಕಿಂತ ದೊಡ್ಡದಾಗಿದ್ದರೆ ನಾವು ಶ್ರೇಣಿಯ ಸಿಂಧುತ್ವವನ್ನು ಎರಡು ಬಾರಿ ಪರಿಶೀಲಿಸುತ್ತೇವೆ, ನಂತರ 1 ಅನ್ನು ಹಿಂತಿರುಗಿ, ಅದು ಅಮಾನ್ಯ ಪ್ರಶ್ನೆಯಾಗಿದೆ. ಇಲ್ಲದಿದ್ದರೆ, ಎಡ ಮತ್ತು ಬಲ ಕ್ರಮವಾಗಿ ಪ್ರಾರಂಭ ಮತ್ತು ಅಂತ್ಯಕ್ಕೆ ಸಮನಾಗಿರುವುದಕ್ಕಿಂತ ಕಡಿಮೆ ಮತ್ತು ಸಮನಾಗಿದ್ದರೆ ನಾವು ಸಿಂಧುತ್ವವನ್ನು ಪರಿಶೀಲಿಸುತ್ತೇವೆ, ನಂತರ ಮರದ ಮೌಲ್ಯವನ್ನು ನೋಡ್‌ನಲ್ಲಿ ಹಿಂತಿರುಗಿಸಿ. ಎಡ ಮಕ್ಕಳ ಮೌಲ್ಯ ಮತ್ತು ಬಲ ಮಕ್ಕಳ ಮೌಲ್ಯವನ್ನು ಪಡೆಯಿರಿ ಮತ್ತು ಈ ಎರಡು ಮೌಲ್ಯಗಳ LCM ಅನ್ನು ಪಡೆಯಿರಿ ಮತ್ತು ಈ ಮೌಲ್ಯವನ್ನು ಹಿಂತಿರುಗಿ.

ಕೋಡ್

ಶ್ರೇಣಿ LCM ಪ್ರಶ್ನೆಗಳಿಗೆ C ++ ಕೋಡ್

#include<iostream>

using namespace std;

#define MAX 1000

int tree[4*MAX];

int arr[MAX];

int GCD(int a, int b)
{
    if (a == 0)
        return b;
    return GCD(b%a, a);
}
int getLCM(int a, int b)
{
    return a*b/GCD(a,b);
}
int solveQuery(int node, int start, int end, int left, int right)
{
    if (end < left || start > right)
        return 1;

    if (left<=start && right >=end)
        return tree[node];

    int mid = (start+end)/2;
    int leftChildgetLCM = solveQuery(2*node, start, mid, left, right);
    int rightChildgetLCM = solveQuery(2*node+1, mid+1, end, left, right);
    return getLCM(leftChildgetLCM, rightChildgetLCM);
}
void buildTree(int node, int start, int end)
{
    if (start==end)
    {
        tree[node] = arr[start];
        return;
    }

    int mid = (start+end)/2;
    buildTree(2*node, start, mid);
    buildTree(2*node+1, mid+1, end);

    int leftChildgetLCM = tree[2*node];
    int rightChildgetLCM = tree[2*node+1];

    tree[node] = getLCM(leftChildgetLCM, rightChildgetLCM);
}

int main()
{
    arr[0] = 2;
    arr[1] = 4;
    arr[2] = 6;
    arr[3] = 9;
    arr[4] = 10;
    arr[5] = 8;
    arr[6] = 7;
    arr[7] = 5;
    arr[8] = 14;
    arr[9] = 1;
    buildTree(1, 0, 9);
    cout << solveQuery(1, 0, 9, 2, 5) << endl;

    cout << solveQuery(1, 0, 9, 3, 7) << endl;

    cout << solveQuery(1, 0, 9, 5, 8) << endl;

    return 0;
}
360
2520
280

ಶ್ರೇಣಿ LCM ಪ್ರಶ್ನೆಗಳಿಗಾಗಿ ಜಾವಾ ಕೋಡ್

class LCMQueries
{

    private static final int MAX = 1000;

    private static int tree[] = new int[4 * MAX];

    private static int arr[] = new int[MAX];

    static int GCD(int a, int b)
    {
        if (a == 0)
        {
            return b;
        }
        return GCD(b % a, a);
    }
    static int getLCM(int a, int b)
    {
        return a * b / GCD(a, b);
    }
    static void buildTree(int node, int start, int end)
    {
        if (start == end)
        {
            tree[node] = arr[start];
            return;
        }

        int mid = (start + end) / 2;
        buildTree(2 * node, start, mid);
        buildTree(2 * node + 1, mid + 1, end);
        int leftChildLCM = tree[2 * node];
        int rightChildLCM = tree[2 * node + 1];

        tree[node] = getLCM(leftChildLCM, rightChildLCM);
    }
    static int solveQuery(int node, int start,
                          int end, int left, int right)
    {
        if (end < left || start > right)
        {
            return 1;
        }

        if (left <= start && right >= end)
        {
            return tree[node];
        }

        int mid = (start + end) / 2;
        int leftChildLCM = solveQuery(2 * node, start, mid, left, right);
        int rightChildLCM = solveQuery(2 * node + 1, mid + 1, end, left, right);
        return getLCM(leftChildLCM, rightChildLCM);
    }
    public static void main(String[] args)
    {
        arr[0] = 2;
        arr[1] = 4;
        arr[2] = 6;
        arr[3] = 9;
        arr[4] = 10;
        arr[5] = 8;
        arr[6] = 7;
        arr[7] = 5;
        arr[8] = 14;
        arr[9] = 1;

        buildTree(1, 0, 9);

        System.out.println(solveQuery(1, 0, 9, 2, 5));

        System.out.println(solveQuery(1, 0, 9, 3, 7));

        System.out.println(solveQuery(1, 0, 9, 5, 8));

    }
}
360
2520
280

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

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

 ಒ (ಲಾಗ್ ಎನ್ * ಲಾಗ್ ಎನ್) ಅಲ್ಲಿ “ಎನ್” ರಚನೆಯ ಅಂಶಗಳ ಸಂಖ್ಯೆ. ಇತರ ಲಾಗ್ ಎನ್ LCM ಅನ್ನು ಕಂಡುಹಿಡಿಯಲು ಬೇಕಾದ ಸಮಯವನ್ನು ಸೂಚಿಸುತ್ತದೆ. ಈ ಸಮಯದ ಸಂಕೀರ್ಣತೆಯು ಪ್ರತಿ ಪ್ರಶ್ನೆಗೆ ಆಗಿದೆ. ಒಟ್ಟು ಸಮಯದ ಸಂಕೀರ್ಣತೆಯಾಗಿದೆ O (N + Q * Log N * log n), ಏಕೆಂದರೆ ಮರವನ್ನು ನಿರ್ಮಿಸಲು ಮತ್ತು ನಂತರ ಪ್ರಶ್ನೆಗಳಿಗೆ ಉತ್ತರಿಸಲು O (N) ಸಮಯ ಬೇಕಾಗುತ್ತದೆ.

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

 ಒ (ಎನ್) ಅಲ್ಲಿ “ಎನ್” ರಚನೆಯ ಅಂಶಗಳ ಸಂಖ್ಯೆ. ವಿಭಾಗದ ಮರವನ್ನು ಸಂಗ್ರಹಿಸಲು ಈ ಸ್ಥಳದ ಅಗತ್ಯವಿದೆ.