მოთხოვნები დიაპაზონის უდიდესი უცნაური გამყოფი XOR– ზე


Რთული ტური საშუალო
ხშირად ეკითხებიან 24 * 7 ინოვაციის ლაბორატორია ციხედ დირექტი Expedia Google ნამდვილად Snapdeal
Array Bits Bitwise-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. სხვა შემთხვევაში დააბრუნეთ divArray- ის XOR [მარჯვნივ] და divArray [მარცხნივ -1].

განმარტება

ჩვენ მივეცით მთელი რიგის მთელი რიგი და ზოგიერთი მოთხოვნა გადასაჭრელად. შემდეგ გვთხოვენ გავერკვიოთ უდიდესი უცნაური გამყოფი XOR- ის შესახებ. მოთხოვნები შეიცავს ორ მთლიან რიცხვს. ეს ნიშნავს, რომ ჩვენ გვაქვს სპექტრი ამ ორ მთლიან რიცხვში. ამისათვის, უპირველეს ყოვლისა, ჩვენ ვადგენთ თითოეული რიცხვის ყველა გამყოფს, მასივის გავლის დროს. შემდეგ ჩვენ ვაპირებთ აიღოს ნომერი მოცემული მასივიდან, ერთდროულად. ჩვენ დავიწყებთ მარყუჟს a, განსაკუთრებით მოცემული ელემენტისთვის. მარყუჟში, ჩვენ გავაგრძელებთ მიმდინარე ელემენტის გაყოფას 2-ზე და განაახლებთ მას თავად ელემენტში. ეს გაგრძელდება მანამ, სანამ ამჟამინდელი ელემენტი არ აღმოჩნდება უცნაური. დრო, როდესაც ნომერი უცნაური გახდება, ჩვენ მარყუჟის გარეთაა.

მასივის ყველა ელემენტის თითოეული გადაკვეთისთვის, დააჭირეთ შედეგს divArray მასივი, სადაც ხდება უცნაური. ისეთი, რომ მასივში იქნება თანაბარი ელემენტი, როგორც მოცემულ მასივში. მაგრამ ყველა გამყოფი არის divArray- ში. მასივის დასრულების შემდეგ გადაკვეთეთ მასივი, რომელშიც ინახება ყველა გამყოფი. ამრიგად, divArray მასივი, რომელიც ინახავს ყველა მნიშვნელობას, არის გამყოფი. შემდეგ ჩვენ ვაპირებთ XOR ოპერაციის შესრულებას divArray მნიშვნელობებზე. ჩვენ ვაპირებთ გავყოთ divArray და XOR ამჟამინდელი ელემენტი და მასივის წინა ელემენტი. ეს ყველაფერი უნდა გაკეთდეს თითოეულ წყვილზე შესრულებულ ოპერაციამდე, როგორც მიმდინარე და წინა მნიშვნელობად.

ასე რომ, როდესაც ჩვენ მოგვეცემა მოთხოვნა, როგორც დიაპაზონი, მარცხნივ და მარჯვნივ. შემდეგ ჩვენ ვაპირებთ შეამოწმოთ, არის თუ არა მარცხენა ნულის ტოლი. შემდეგ დააბრუნეთ divArray [მარჯვნივ], წინააღმდეგ შემთხვევაში, ჩვენ ვაპირებთ დაბრუნების XOR divArray [მარჯვნივ] და divArray [მარცხნივ -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

სირთულის ანალიზი

დროის სირთულე

O (N log n) სადაც "N" არის მასივის ელემენტების რაოდენობა. და არის მასივის ჟურნალში არსებული რიცხვი, რომელსაც აქვს ბაზა 2. log n ფაქტორი არის რიცხვის გაყოფის გამო, სანამ არ მივიღებთ უცნაურ გამყოფს.

სივრცის სირთულე

O (N) სადაც "N" არის მასივის ელემენტების რაოდენობა. ჩვენ გამოვიყენეთ მასივი xor მნიშვნელობების შესანახად, რომელიც ადგილს იკავებს.