रेंज के सबसे बड़े अजीब भाजक के XOR पर प्रश्न  


कठिनाई स्तर मध्यम
में अक्सर पूछा 24 * 7 इनोवेशन लैब्स गढ़ डायरेक्टी Expedia गूगल वास्तव में स्नैपडील
ऐरे बिट्स बिटवाइज- XOR क्वेरी की समस्या

समस्या का विवरण  

समस्या "श्रेणी के सबसे बड़े विचित्र XOR पर प्रश्न" में कहा गया है कि आपको ए सरणी of पूर्णांक और क्वेरी q, प्रत्येक क्वेरी में एक सीमा होती है। समस्या कथन प्रत्येक प्रश्न के लिए दिए गए सीमा के भीतर सबसे बड़ा अजीब भाजक का XOR पता लगाने के लिए कहता है।

उदाहरण  

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 वर्तमान तत्व के XOR और divArray सरणी के पिछले तत्व के लिए सरणी।
  3. जांचें कि यदि बायां तत्व 0 के बराबर है, तो divArray [दाएं] वापस करें।
  4. एल्स ने डी'अर्इरे [दायें] और दिआरे्रे [लेफ्ट -1] के एक्सओआर को वापस किया।

व्याख्या

हमने पूर्णांक और कुछ प्रश्नों को हल करने के लिए एक सरणी दी है। फिर हमें सबसे बड़े अजीब भाजक के XOR का पता लगाने के लिए कहा जाता है। प्रश्नों में दो पूर्णांक होते हैं। तो, इसका मतलब है कि हमारे पास उन दो पूर्णांकों के भीतर एक सीमा है। इसके लिए, सबसे पहले, हम एरे को ट्रेस करते हुए, प्रत्येक संख्या के सभी विभाजकों को खोजने जा रहे हैं। फिर हम एक बार में दिए गए एरे से नंबर लेने जा रहे हैं। हम विशेष रूप से दिए गए तत्व के लिए एक लूप शुरू करेंगे। लूप में, हम वर्तमान तत्व को 2 से विभाजित करेंगे और इसे तत्व में ही अपडेट करेंगे। यह बात तब तक चलेगी जब तक कि वर्तमान तत्व विषम नहीं पाया जाता। जिस समय संख्या विषम हो जाएगी, हम लूप के बाहर तोड़ देंगे।

यह भी देखें
विशिष्ट अंतर के साथ जोड़े की अधिकतम राशि

किसी सरणी के प्रत्येक तत्व के प्रत्येक ट्रैवर्सल के लिए, परिणाम को अंदर धकेलें DivArray सरणी, जहां यह विषम हो जाता है। जैसे कि किसी सरणी में एक समान तत्व होगा जैसा कि किसी दिए गए सरणी में हैं। लेकिन सभी भाजक वहाँ के divArray में हैं। सरणी के पूरा होने के बाद, उस सरणी को पार करें जिसमें सभी भाजक संग्रहीत हैं। इस प्रकार, divArray सरणी जो सभी मानों को संग्रहीत कर रही है वह भाजक है। तब हम डिवोर्स वैल्यू पर XOR ऑपरेशन करने जा रहे हैं। हम divArray, और XOR को वर्तमान तत्व और सरणी के पिछले तत्व के पार करने जा रहे हैं। और इस चीज को तब तक किया जाना चाहिए जब तक कि प्रत्येक जोड़ी पर वर्तमान और पिछले मूल्य के रूप में किए गए ऑपरेशन।

इसलिए, जब हमें एक सीमा के रूप में एक क्वेरी दी जाती है, तो बाएं और दाएं। फिर हम जांचने वाले हैं कि क्या बाएं शून्य के बराबर है। इसके बाद divArray को वापस करें [दाईं ओर], अन्यथा हम divarrray [right] और divArray [left-1] का XOR लौटाने जा रहे हैं।

कोड  

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

जावा कोड श्रेणी के सबसे बड़े विचित्र भाजक पर प्रश्न का उत्तर देने के लिए

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

जटिलता विश्लेषण  

समय जटिलता

ओ (एन लॉग एन) जहां "एन" सरणी में तत्वों की संख्या है। तथा सरणी संख्या में मौजूद संख्या में आधार होता है 2. लॉग एन फैक्टर संख्या के विभाजन के कारण होता है जब तक कि हमें एक अजीब विभाजक नहीं मिलता है।

यह भी देखें
समान ऐरे एलीमेंट्स लेटकोड सॉल्यूशन के लिए न्यूनतम चाल

अंतरिक्ष जटिलता

पर) जहां "एन" सरणी में तत्वों की संख्या है। हमने xor वैल्यूज़ को स्टोर करने के लिए एक ऐरे का इस्तेमाल किया है जो स्पेस ले रहा है।