श्रेणीच्या सर्वात विचित्र भागाच्या XOR वर क्वेरी


अडचण पातळी मध्यम
वारंवार विचारले 24 * 7 इनोव्हेशन लॅब किल्ला डायरेक्टि यामध्ये Google खरंच Snapdeal
अरे बिट्स बिटवाइज-एक्सओआर क्वेरी समस्या

समस्या विधान

"श्रेणीच्या सर्वात विचित्र भागाच्या एक्सओआरवरील क्वेरीज" समस्या आपल्याला असे दिली गेली आहे की अॅरे of पूर्णांक आणि क्वेरी q, प्रत्येक क्वेरीमध्ये श्रेणी असते. प्रॉब्लेम स्टेटमेंटमध्ये प्रत्येक क्वेरीसाठी दिलेल्या श्रेणीतील सर्वात मोठे विषम विभाजक चे एक्सओआर शोधण्यास सांगितले जाते.

उदाहरण

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

स्पष्टीकरण

सर्वात विचित्र विभाजक: (1,3,1)

3,1 चा XOR 2 आहे.

1,3 चा XOR 2 आहे.

श्रेणीच्या सर्वात विचित्र भागाच्या XOR वर क्वेरी

 

अल्गोरिदम

  1. दिलेल्या अ‍ॅरेचा आढावा घ्या.
    1. अ‍ॅरेचा वर्तमान घटक विचित्र असल्यास तो तपासून पहा आणि कमीतकमी विभाजक संख्येने वर्तमान घटकाचे अद्यतनित करा.
    2. सेट करा DivArray दिलेल्या अ‍ॅरेच्या अद्यतन घटकाचा घटक.
  2. अ‍ॅरेचा पुन्हा आढावा घ्या आणि प्रत्येक घटक अद्यतनित करा DivArray वर्तमान घटकाच्या एक्सओआर आणि डिव्हॅरे अ‍ॅरेच्या मागील घटकाचे अ‍ॅरे.
  3. डावा घटक 0 च्या बरोबर असल्याचे तपासा, तर DivArray [उजवीकडे] परत करा.
  4. अन्यथा DivArray [उजवीकडे] आणि DivArray [डावे -1] चे XOR परत करा.

स्पष्टीकरण

आम्ही निराकरण करण्यासाठी पूर्णांकांची अ‍ॅरे आणि काही क्वेरी दिल्या आहेत. मग आम्हाला सर्वात विचित्र भागाचे XOR शोधण्यास सांगितले जाते. क्वेरींमध्ये दोन पूर्णांक असतात. तर, याचा अर्थ असा की आपल्याकडे त्या दोन पूर्णांकांमधील एक श्रेणी आहे. यासाठी, अ‍ॅरेचा मागोवा घेताना आपण प्रथम प्रत्येक संख्येचे सर्व विभाजक शोधणार आहोत. मग आम्ही एका वेळी दिलेल्या अ‍ॅरेमधून नंबर निवडणार आहोत. विशेषतः दिलेल्या घटकासाठी आपण एक लूप सुरू करू. लूपमध्ये आपण सध्याचे घटक 2 ने विभाजित करू आणि त्यास घटकामध्येच अद्यतनित करू. वर्तमान घटक विचित्र असल्याचे आढळत नाही तोपर्यंत ही गोष्ट चालूच राहिल. जेव्हा संख्या विचित्र होईल, आम्ही लूपच्या बाहेर खंडित करतो.

अ‍ॅरेच्या प्रत्येक घटकाच्या प्रत्येक ट्रॅव्हर्सलसाठी, परिणामी पुढे ढकलणे DivArray अ‍ॅरे, जिथे ते विचित्र होते. जसे की दिलेल्या अ‍ॅरेमध्ये जसे अ‍ॅरेमध्ये समान घटक असतील. परंतु सर्व भागाकार DivArray मध्ये आहेत. अ‍ॅरे पूर्ण झाल्यानंतर अ‍ॅरेला मागे टाका ज्यामध्ये सर्व डिव्हिव्हर्स साठवले आहेत. अशा प्रकारे, सर्व व्हॅल्यूज संग्रहित करणारे डिव्हॅरे अ‍ॅरे म्हणजे विभाजक. तर आपण DivArray च्या व्हॅल्यूजवर XOR ऑपरेशन करणार आहोत. आम्ही DivArray, आणि वर्तमान घटक आणि अ‍ॅरेचा मागील घटक XOR पार करणार आहोत. आणि प्रत्येक जोडीवर चालू आणि मागील मूल्य म्हणून ऑपरेशन होईपर्यंत ही गोष्ट केली पाहिजे.

जेव्हा जेव्हा आपल्याला श्रेणी, डावी आणि उजवीकडील क्वेरी दिली जाते. तर डावीकडून शून्य आहे का ते तपासणार आहोत. नंतर DivArray [उजवीकडे] परत करा, अन्यथा आपण DivArray [उजवीकडे] आणि DivArray [डावे -1] चा XOR परत करणार आहोत.

कोड

श्रेणीच्या सर्वात विचित्र भागाच्या XOR वरील प्रश्नांची उत्तरे देण्यासाठी C ++ कोड

#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

गुंतागुंत विश्लेषण

वेळ कॉम्प्लेक्सिटी

ओ (एन लॉग एन) जेथे “एन” अ‍ॅरे मधील घटकांची संख्या. आणि अ‍ॅर लॉग मध्ये अस्तित्त्वात असलेली संख्या म्हणजे बेस २. लॉग एन फॅक्टर संख्येच्या विभाजनामुळे आहे जोपर्यंत आपल्याला विचित्र विभाजक मिळत नाही.

स्पेस कॉम्प्लेक्सिटी

ओ (एन) जेथे “एन” अ‍ॅरे मधील घटकांची संख्या. आम्ही जागा घेत असलेल्या झोर व्हॅल्यूज संग्रहित करण्यासाठी अ‍ॅरे वापरली आहे.