శ్రేణి యొక్క గొప్ప బేసి విభజన యొక్క 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 ను తిరిగి ఇవ్వండి.

వివరణ

మేము పూర్ణాంకాల శ్రేణిని మరియు పరిష్కరించడానికి కొన్ని ప్రశ్నలను ఇచ్చాము. అప్పుడు గొప్ప బేసి డివైజర్ యొక్క XOR ను కనుగొనమని అడుగుతారు. ప్రశ్నలలో రెండు పూర్ణాంకాలు ఉంటాయి. కాబట్టి, ఆ రెండు పూర్ణాంకాలలో మనకు ఒక పరిధి ఉందని అర్థం. దీని కోసం, మొదట, మేము శ్రేణిలో ప్రయాణిస్తున్నప్పుడు, ప్రతి సంఖ్య యొక్క అన్ని విభజనలను కనుగొనబోతున్నాము. అప్పుడు మేము ఇచ్చిన శ్రేణి నుండి ఒక సమయంలో సంఖ్యను తీసుకోబోతున్నాము. మేము ఒక, ముఖ్యంగా ఇచ్చిన మూలకం కోసం లూప్‌ను ప్రారంభిస్తాము. లూప్‌లో, ప్రస్తుత మూలకాన్ని 2 ద్వారా విభజించి, మూలకంలోనే దాన్ని నవీకరిస్తాము. ప్రస్తుత మూలకం బేసిగా కనిపించని వరకు ఈ విషయం కొనసాగుతుంది. సంఖ్య బేసిగా మారే సమయం, మేము లూప్ వెలుపల విచ్ఛిన్నం చేస్తాము.

శ్రేణి యొక్క ప్రతి మూలకం యొక్క ప్రతి అడ్డంగా, ఫలితాన్ని లోపలికి నెట్టండి divArray శ్రేణి, అది బేసి అవుతుంది. ఇచ్చిన శ్రేణిలో ఉన్నట్లుగా శ్రేణిలో సమాన మూలకం ఉంటుంది. కానీ డివైజర్లన్నీ దివారేలో ఉన్నాయి. శ్రేణి పూర్తయిన తరువాత, అన్ని విభజనలను నిల్వ చేసిన శ్రేణిని దాటండి. ఈ విధంగా, అన్ని విలువలను నిల్వచేసే divArray శ్రేణి విభజన. అప్పుడు మేము divArray విలువలపై XOR ఆపరేషన్ చేయబోతున్నాం. మేము divArray మరియు XOR ప్రస్తుత మూలకం మరియు శ్రేణి యొక్క మునుపటి మూలకాన్ని దాటబోతున్నాము. ప్రస్తుత మరియు మునుపటి విలువగా ప్రతి జతపై ఆపరేషన్ చేసే వరకు ఈ పని చేయాలి.

కాబట్టి, మనకు ఒక పరిధి, ఎడమ మరియు కుడివైపు ప్రశ్న ఇచ్చినప్పుడు. అప్పుడు మనం ఎడమ సున్నాకి సమానంగా ఉందో లేదో తనిఖీ చేయబోతున్నాం. అప్పుడు divArray [కుడి] ను తిరిగి ఇవ్వండి, లేకపోతే మేము divArray [కుడి] మరియు divArray [left-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

సంక్లిష్టత విశ్లేషణ

సమయం సంక్లిష్టత

O (N లాగ్ n) (ఇక్కడ  “ఎన్” శ్రేణిలోని మూలకాల సంఖ్య. మరియు శ్రేణి లాగ్‌లో ఉన్న సంఖ్య బేస్ 2 ను కలిగి ఉంది. లాగ్ n కారకం మనకు బేసి డివైజర్ వచ్చేవరకు సంఖ్య యొక్క విభజన కారణంగా ఉంటుంది.

అంతరిక్ష సంక్లిష్టత

పై) (ఇక్కడ  “ఎన్” శ్రేణిలోని మూలకాల సంఖ్య. స్థలాన్ని తీసుకుంటున్న xor విలువలను నిల్వ చేయడానికి మేము శ్రేణిని ఉపయోగించాము.