XOR ოპერაცია მასივის Leetcode ხსნარში


Რთული ტური Easy
ხშირად ეკითხებიან Walmart Labs
Array ბიტის მანიპულირება Bits Bitwise-XOR

პრობლემის განცხადება

ამ პრობლემის დროს ჩვენ უნდა გავაკეთოთ XOR ოპერაცია n ზომის მასივში, რომელშიც თითოეული ელემენტი ტოლია (დაწყება + 2 * i), სადაც i არის ელემენტის ინდექსი (0 ინდექსში) და მოცემულია დაწყების მნიშვნელობა.
ჩვენ უნდა დავაბრუნოთ მასივის ყველა ელემენტის bitwise XOR.

მაგალითი

n = 4, start = 3
8

განმარტება:

მასივის ნომრები უდრის [3, 5, 7, 9] სადაც (3 ^ 5 ^ 7 ^ 9) = 8.
სადაც "^" შეესაბამება bitwise XOR ოპერატორს.

n = 1, start = 7
7

განმარტება:

მასივის რიცხვები უდრის [7] -ს, მაშასადამე xor = 7.

მიდგომა (უხეში ძალა)

ჩვენ შეგვიძლია უბრალოდ გავუშვათ for loop n ჯერ i = 0-დან i = n-1-მდე. მარყუჟისთვის ჩვენ გავაკეთებთ bitwise xor- ს (დაწყება + 2 * i) მიმდინარე xor- ით, რომელსაც ვინახავთ ცვლად res- ში.

ალგორითმი

1. შევქმნათ ind ცვლადი, რომელიც წარმოადგენს მასივის ელემენტის ინდექსს და ინიცირდება 0-ით.
2. შევქმნათ ცვლადი res, რომ შევინახოთ მიმდინარე xor მარყუჟის დროს და დავიწყოთ 0-ით.
3. აწარმოეთ for მარყუჟი ind = 0 – დან ind = n – 1 – მდე.
4. გავაკეთოთ res– ის xor bit (დაწყება + 2 * i), ანუ ელემენტი ინდექსში და შეინახეთ შედეგი res– ში.
5. დააბრუნე რეს.

XOR ოპერაციის განხორციელება მასივის Leetcode Solution- ში

C ++ პროგრამა

#include <bits/stdc++.h>
using namespace std;

int xorOperation(int n, int start) {

    int ind=0;
    int res=0;
    for(ind=0;ind<n;ind++) res=res^(start+2*ind);

    return res;

}
int main() 
{
        int n=4;
        int start=3;
    cout<<xorOperation(n,start)<<endl;

  return 0; 
}
8

ჯავა პროგრამა

import java.lang.*;

class XorOperation
{  
    public static int xorOperation(int n, int start) 
    {

        int ind=0;
        int res=0;
        for(ind=0;ind<n;ind++) res=res^(start+2*ind);

        return res;      
    }
    
    
    public static void main(String args[])
    {
        int n=4;
        int start=3;

        System.out.println(xorOperation(n,start));
        
    }
}
8

სირთულის ანალიზი XOR ოპერაციისთვის მასივის Leetcode ხსნარში

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

O (N):  სადაც N არის მასივის მოცემული ზომა. როგორც მასივს ვათვალიერებთ N ელემენტის მარყუჟის ერთეულში. ამრიგად, დროის სირთულე არის O (N).

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

O (1):  რადგან ჩვენ არ ვიყენებთ დამატებით მეხსიერებას, გარდა ზოგიერთი ცვლადისა. ამრიგად, გამოყენებული დამატებითი სივრცე მუდმივია.

მიდგომა (ბიტის მანიპულირება)

ზემოხსენებულ პრობლემას ვხედავთ, რომ სხვაობა თითოეულ მომდევნო ელემენტს შორის არის 2. ეს ნიშნავს, რომ ან ყველა ელემენტი იქნება ლუწი, ან ყველა უცნაური იქნება. ეს ქმნის ერთგვარ დიაპაზონს, მაგრამ არა თანმიმდევრული, ანუ აქვს ალტერნატიული მნიშვნელობები.

ბიტიანი მანიპულაციის გამოყენებით ჩვენ შეგვიძლია ვიპოვოთ დიაპაზონის bitwise xor, რომელსაც აქვს მუდმივი ელემენტები მუდმივ დროში. მოდით ვნახოთ როგორ და შემდეგ შევეცდებით ზემოთ მოცემული პრობლემა გადავაქციოთ ქვემოთ მოცემულ პრობლემად:

მოდით ვივარაუდოთ დიაპაზონი = [3,4,5,6,7,8,9,10], და xor უნდა გამოვიყენოთ პირველ და ბოლო ელემენტს შორის დიაპაზონში.

მოდით x იყოს ნებისმიერი ლუწი რიცხვი და y იყოს რიცხვი xie y = x + 1-ის გვერდით. მარტივად შეგვიძლია გავაანალიზოთ, რომ x და y xor ყოველთვის იქნება 1. ან xor თითოეული ლუწი რიცხვისა და მის გვერდით კენტი რიცხვი ყოველთვის არის 1. აქედან გამომდინარე, შეგვიძლია დავასკვნათ, რომ პირველ და ბოლო რიცხვს შორის ყოველი ლუწი კენტი წყვილი xor ტოლია 1
i.e.   4^5=1,  6^7=1,  8^9=1

თუ ამ წყვილების რაოდენობა კენტია, მაშინ ელემენტები xor 1-ლი ლუწი რიცხვიდან და ბოლო კენტი რიცხვი იქნება 1, ანდა 0.
ანუ 4 ^ 5 ^ 6 ^ 7 ^ 8 ^ 9 = 1 ^ 1 ^ 1 = 1

ახლა ჩვენ მხოლოდ პოზიციები დაგრჩა ბოლოს პოზიციებზე, რომლებიც არის 3 და 10. აქედან გამომდინარე, ჩვენი პასუხი იქნება 3 ^ 1 ^ 10 = 8, როგორც ნაჩვენებია ქვემოთ მოცემულ ფიგურაში:

XOR ოპერაცია მასივის Leetcode ხსნარში

პრობლემის გადაქცევა ზედიზედ XOR დიაპაზონში

ზემოხსენებულ პრობლემაში ჩვენ შეგვიძლია შევამციროთ მანძილი თითოეულ ელემენტს შორის 2 – დან 1 – მდე მარჯვნივ ცვლა ბიტიურად თითოეული ელემენტი 1-ზე (იგივე იყოფა 2-ზე). ამით ჩვენ მხოლოდ ელემენტების ბოლო ნაწილზე ვმოქმედებთ. ასე რომ, ჩვენ პირველად ვინახავთ ჩვენი პასუხის ბოლო ნაწილს შემდეგი შემთხვევებით:

1. თუ მასივის ყველა ელემენტი კენტია და ელემენტების საერთო რაოდენობაც კენტია, მაშინ lastbit = 1.
2. სხვა ბოლო ბიტი = 0.

მას შემდეგ, რაც თითოეულ ელემენტს მარჯვნივ გადავიტანთ 1-ით, ჩვენი დიაპაზონი ხდება:

დაწყება / 2, დაწყება / 2 +1, დაწყება / 2 +2,. . . . , დაწყება / 2 + (n-1).

სადაც პირველი = დაწყება / 2 და ბოლო = დაწყება / 2 + (n-1).

ახლა ჩვენ შეგვიძლია მარტივად გავერკვეთ ამ დიაპაზონის xor- ზე, ვიპოვოთ ბოლო ელემენტების bitwise xor და მათ შორის ყველა ლუწი კენტი წყვილი მუდმივ დროში.

Xor– ის პოვნის შემდეგ უნდა bitwise მარცხენა ცვლა შედეგის 1-ით მისაღებად ბიტების თავდაპირველი პოზიცია ჩვენს საბოლოო პასუხში. ბოლოს დაამატეთ ბოლო ბიბიტი შედეგს და დააბრუნეთ იგი.

XOR ოპერაციის განხორციელება მასივის Leetcode Solution- ში

C ++ პროგრამა

#include <bits/stdc++.h>
using namespace std;

int xorOperation(int n, int start) {

    int lastbit;
    if(n%2==1  &&  start%2==1) lastbit=1;
    else lastbit=0;

    //after 1 right shift
    int first= start/2;
    int last= start/2+ n-1;

    int res=0;

    if(first%2==1)
    { 
        res^=first; 
        first++;
    }

    if(last%2==0)
    {
        res^=last;
        last--;
    }


    int pairs=0;            //in between pairs
    if(first<last)   pairs= (last-first+1)/2;    
    if(pairs%2==1) res^=1;   

    res<<=1;                // back to 1 left shift
    res+=lastbit;           // attaching last bit

    return res;

}
int main() 
{
        int n=4;
        int start=3;
    cout<<xorOperation(n,start)<<endl;

  return 0; 
}
8

ჯავა პროგრამა

import java.lang.*;

class Rextester
{  
    public static int xorOperation(int n, int start) 
    {

        int lastbit;
        if(n%2==1  &&  start%2==1) lastbit=1;
        else lastbit=0;

        //after 1 right shift
        int first= start/2;
        int last= start/2+ n-1;

        int res=0;

        if(first%2==1)
        { 
            res^=first; 
            first++;
        }

        if(last%2==0)
        {
            res^=last;
            last--;
        }


        int pairs=0;            //in between pairs
        if(first<last)   pairs= (last-first+1)/2;    
        if(pairs%2==1) res^=1;   

        res<<=1;                // back to 1 left shift
        res+=lastbit;           // attaching last bit

        return res;     
    }
    
    
    public static void main(String args[])
    {
        int n=4;
        int start=3;

        System.out.println(xorOperation(n,start));
        
    }
}
8

სირთულის ანალიზი XOR ოპერაციისთვის მასივის Leetcode ხსნარში

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

O (1):  რადგან მასალის ყველა ელემენტს არ გადავხედავთ, ბიტიანი მანიპულაციის გამოყენებით ჩვენ ეს გავაკეთეთ მუდმივ დროში.

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

O (1):  აქ ასევე გამოყენებულია დამატებითი მეხსიერება მუდმივი.