פֿראגן אויף XOR פון די גרעסטע מאָדנע דיוויזאָר פון דער ריי


שוועריקייט לעוועל מיטל
אָפט געבעטן אין 24 * 7 יננאָוואַטיאָן לאַבס ציטאַדעל דירעקטי עקספּעדיאַ גוגל טאקע סנאַפּדעאַל
מענגע ביץ ביטוויסע-קסאָר אָנפֿרעג פּראָבלעם

פּראָבלעם סטאַטעמענט

די פּראָבלעם "פֿראגן אויף XOR פון די גרעסטע מאָדנע דיוויזאָר פון די קייט" שטאַטן אַז איר באַקומען אַן מענגע of ינטעגער און אָנפֿרעג q, יעדער אָנפֿרעג באשטייט פון אַ קייט. די פּראָבלעם ויסזאָגונג איז צו געפֿינען די XOR פון די גרעסטע מאָדנע דיווייסער אין די געגעבן קייט פֿאַר יעדער אָנפֿרעג.

בייַשפּיל

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

דערקלערונג

גרעסטע מאָדנע דיוויזאָר: (1,3,1)

XOR פון 3,1 איז 2.

XOR פון 1,3 איז 2.

פֿראגן אויף XOR פון די גרעסטע מאָדנע דיוויזאָר פון דער ריי

 

אַלגאָריטהם

  1. אַריבער די געגעבן מענגע.
    1. קעסיידער קאָנטראָלירן דעם קראַנט עלעמענט פון אַ מענגע אויב עס איז מאָדנע און דערהייַנטיקן דעם קראַנט עלעמענט דורך די מינדסטער דיווייסער נומער.
    2. שטעלן די divArray עלעמענט צו דער דערהייַנטיקן עלעמענט פון אַ געגעבן מענגע.
  2. אַריבער די מענגע ווידער און דערהייַנטיקן יעדער עלעמענט פון divArray מענגע צו די XOR פון די קראַנט עלעמענט און די פריערדיקע עלעמענט פון דיוויי אַררייַ.
  3. קאָנטראָלירן אויב די לינקס עלעמענט איז גלייַך צו 0, דאַן צוריק די divArray [רעכט].
  4. אַנדערש צוריקקומען די XOR פון divArray [רעכט] און divArray [לינקס -1].

דערקלערונג

מיר האָבן באַשטימט אַ פּלאַץ פון ינטאַדזשערז און עטלעכע פֿראגן צו סאָלווע. דערנאָך מיר ווערן געבעטן צו געפֿינען די XOR פון די גרעסטע מאָדנע דיוויזאָר. די פֿראגן אַנטהאַלטן צוויי ינטאַדזשערז. אַזוי, עס מיטל אַז מיר האָבן אַ קייט אין די צוויי ינטאַדזשערז. פֿאַר דעם, ערשטער פון אַלע, מיר וועלן געפֿינען אַלע די דיווייסערז פון יעדער נומער בשעת דורכפאָר די מענגע. דערנאָך מיר וועלן קלייַבן די נומער פון אַ געגעבן מענגע אין אַ צייט. מיר וועלן אָנהייבן אַ שלייף פֿאַר אַ באַזונדער עלעמענט. אין די שלייף, מיר וועלן פאָרזעצן צו טיילן די קראַנט עלעמענט דורך 2 און דערהייַנטיקן עס אין דעם עלעמענט זיך. די זאַך וועט פאָרזעצן ביז די קראַנט עלעמענט איז נישט ומגעוויינטלעך. ווען די נומער וועט ווערן מאָדנע, מיר ברעכן אַרויס די שלייף.

שטופּן די רעזולטאַט פֿאַר יעדער דורכפאָר פון יעדער עלעמענט פון אַ מענגע divArray מענגע, ווו עס ווערט מאָדנע. אַזאַ אַז עס וועט זיין אַן גלייַך עלעמענט אין אַ מענגע ווי עס זענען אין אַ געגעבן מענגע. אָבער אַלע די דיווייסערז זענען דאָרט אין די דיוויי. נאָך די קאַמפּלישאַן פון די מענגע, אַריבער די מענגע אין וואָס אַלע דיווייסערז זענען סטאָרד. אַזוי, די דיווייס מענגע וואָס סטאָרד אַלע די וואַלועס איז די דיווייסערז. דערנאָך מיר וועלן דורכפירן די XOR אָפּעראַציע אויף די דיואַררייַ וואַלועס. מיר וועלן דורכגיין די divArray און XOR דעם קראַנט עלעמענט און די פריערדיקע עלעמענט פון די מענגע. און דעם זאַך זאָל זיין געטאן ביז די אָפּעראַציע וואָס איז פּערפאָרמד אויף יעדער פּאָר ווי די קראַנט און פרייַערדיק ווערט.

אַזוי ווען מיר באַקומען אַ אָנפֿרעג ווי אַ קייט, לינקס און רעכט. דערנאָך מיר וועלן קאָנטראָלירן צי די לינקס איז גלייַך צו נול. דערנאָך צוריקקומען דיואַררייַ [רעכט], אַנדערש מיר וועלן צוריקקומען די XOR פון דיוואַררייַ [רעכט] און דיוואַררייַ [לינקס -1].

קאָדעקס

C ++ קאָד צו ענטפֿערן פֿראגן אויף XOR פון די גרעסטע מאָדנע דיוויזאָר פון די קייט

#include<iostream>

using namespace std;

void getDivisorArray(int arr[], int divArray[], int n)
{
    for (int i = 0; i < n; i++)
    {
        while (arr[i] % 2 != 1)
            arr[i] /= 2;

        divArray[i] = arr[i];
    }
    for (int i = 1; i < n; i++)
        divArray[i] = divArray[i - 1] ^ divArray[i];
}

int solveQuery(int divArray[], int left, int right)
{
    if (left == 0)
        return divArray[right];
    else
        return divArray[right] ^ divArray[left - 1];
}

int main()
{
    int arr[] = {2, 6, 4};
    int n = sizeof(arr) / sizeof(arr[0]);

    int divArray[n];
    getDivisorArray(arr, divArray, n);

    cout << solveQuery(divArray, 1, 2) << endl;
    cout << solveQuery(divArray, 0, 1) << endl;

    return 0;
}
2
2

דזשאַוואַ קאָד צו ענטפֿערן פֿראגן אויף XOR פון די גרעסטע מאָדנע דיוויזאָר פון דער ריי

class QueriesXOR
{
    public static void getDivisorArray(int arr[], int divArray[], int n)
    {
        for (int i = 0; i < n; i++)
        {
            while (arr[i] % 2 != 1)
                arr[i] /= 2;

            divArray[i] = arr[i];
        }
        for (int i = 1; i < n; i++)
            divArray[i] = divArray[i - 1] ^ divArray[i];
    }
    
    static int solveQuery(int divArray[], int l, int r)
    {
        if (l == 0)
            return divArray[r];
        else
            return divArray[r] ^ divArray[l - 1];
    }
    
    public static void main (String[] args)
    {
        int arr[] = {2, 6, 4};
        int n = arr.length;

        int divArray[] = new int[n];
        getDivisorArray(arr, divArray, n);

        System.out.println(solveQuery(divArray, 1, 2)) ;
        System.out.println (solveQuery(divArray, 0, 1));
    }
}
2
2

קאַמפּלעקסיטי אַנאַליסיס

צייט קאַמפּלעקסיטי

אָ (N קלאָץ n) ווו "N" איז די נומער פון עלעמענטן אין די מענגע. און איז די נומער פאָרשטעלן אין די מענגע קלאָץ האט באַזע 2. דער קלאָץ n פאַקטאָר איז ווייַל פון די אָפּטייל פון נומער ביז מיר באַקומען אַן מאָדנע דיוויזאָר.

ספעיס קאַמפּלעקסיטי

אָ (N) ווו "N" איז די נומער פון עלעמענטן אין די מענגע. מיר האָבן געניצט אַ מענגע צו קראָם די XOR וואַלועס וואָס נעמען די פּלאַץ.