שאילתות טווח LCM


רמת קושי קשה
נשאל לעתים קרובות אמזון בעברית דירקטי Google אכן פייפאל Snapdeal סופר
מערך בעיית שאילתות פלח-עץ עֵץ

הצהרת בעיה

הבעיה "שאילתות טווח LCM" קובעת שיש לך מספר שלם מערך ו q מספר שאילתות. כל שאילתה מכילה את (שמאל, ימין) כטווח. המשימה הנתונה היא לברר את ה- LCM (שמאל, ימין), כלומר LCM של כל המספר שמגיע בטווח של שמאל וימין כולל.

דוגמה

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

הסבר

עבור (2,5) ה- LCM של 6,9,10 ו- 8 הוא 360

עכשיו שוב לשאילתה הבאה כלומר, (3,7), LCM של 9,10,8,7 ו- 5 הוא 2520

ולבסוף עבור (5,8) LCM של 8,7,5 ו- 14 יהיה 280

שאילתות טווח LCM

 

אַלגוֹרִיתְם

  1. הכריזו על שניים מה- מערכים.
  2. בנה עץ פלח על ידי קריאה רקורסיבית לפונקציות עבור הילד השמאלי והילד הימני.
  3. קבל את ה- LCM לצומת הילד השמאלי ולצומת הילד הימני.
  4. כדי לקבל את ה- LCM של מספר, חלק את המוצר של הילד השמאלי והילד הימני לפי ה- GCD שלהם.
  5. עבור כל שאילתה כשמאל וכימנית, בדוק אם הטווח אינו תקף ואז החזר 1, אחרת בדוק אם השמאל קטן מערך ההתחלה של הצומת והימני גדול מערכו של צומת הסיום, ואז החזיר את צומת הערך הנוכחי של העץ.
  6. אם אחד מהתנאים שלמעלה אינו נכון, אחרת התקשר רקורסיבית לפונקציה כדי לקבל את הצומת השמאלי lcm ואת הצומת הימני lcm ואז התקשר לפונקציה lcm כדי לקבל את LCM של המספרים האלה.

הסבר

ניתן מערך שלם וכמה שאילתות עם טווח שמאל וימין. גלה את LCM מכל המספרים בטווח כולל. כדי לגלות את ה- lcm מיישמים את הנוסחה כ- LCM של arr [שמאל, שמאל + 1, ……., ימין -1, ימין], אך בזה נשתמש בעץ. אנו הולכים לבנות עץ פלח. נבדוק אם יש רק ערך אחד במערך, ואז נכניס את הערך המסוים הזה לצומת העץ. אחרת, אנו הולכים לפצל את המערך לשניים ולהתחיל לבנות את העץ, לצומת הילד השמאלי. לאחר מכן העבירו את הערכים כצומת 2 * עבור הצומת השמאלי, ולצומת הילד הימני, 2 * הצומת + 1 וקבלו את ה- LCM של הערך על ידי העברתו לפונקציה getLCM. וקבל את ה- LCM של שני צמתי הילד האלה ואחסן את הערך החזר במיקום הצומת של העץ.

בפונקציה LCM, אנו הולכים למצוא את המחלק המשותף הגדול ביותר של ערכי צומת שמאל וימין. ואז נחזיר את המוצר של חלוקת המוצר של הצמתים השמאלי והימני ואת המחלק המשותף הגדול ביותר של הצומת השמאלי והימני.

עבור כל שאילתה נקבל כמיקום שמאלי וימין, נבדוק פעמיים את תוקף הטווח אם ערך הסיום קטן משמאל או שער ההתחלה גדול מימין, ואז נחזיר 1, זו שאלה לא חוקית. אחרת, נבדוק את התוקף אם שמאל וימין פחות שווים וגדולים משווים להתחלה ולסיום בהתאמה, ואז נחזיר את ערך העץ בצומת. השג את ערך הילד השמאלי ואת ערך הילד הימני וקבל את ה- LCM של שני הערכים הללו והחזיר ערך זה.

קופונים

קוד C ++ לשאילתות טווח LCM

#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

קוד Java עבור שאילתות טווח 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

ניתוח מורכבות

מורכבות זמן

 O (יומן N * יומן n) איפה "N" הוא מספר האלמנטים במערך. האחר יומן n מציין את הזמן הנדרש למציאת ה- LCM. מורכבות הזמן הזו היא לכל שאילתה. מורכבות הזמן הכוללת היא O (N + Q * יומן N * יומן n), זאת מכיוון שנדרש זמן O (N) לבניית העץ ואז לענות על השאלות.

מורכבות בחלל

 עַל) איפה "N" הוא מספר האלמנטים במערך. שטח זה נדרש לאחסון עץ הקטע.