অ্যারে লেটকোড সলিউশনে এক্সওআর অপারেশন


কাঠিন্য মাত্রা সহজ
প্রায়শই জিজ্ঞাসা করা হয় ওয়ালমার্ট ল্যাব
বিন্যাস বিট ম্যানিপুলেশন বিটস বিটওয়াইস-এক্সওআর

সমস্যা বিবৃতি

এই সমস্যায় আমাদের সাইজের এন এর অ্যারে XOR অপারেশন করতে হবে যেখানে প্রতিটি উপাদান সমান (শুরু + 2 * i) যেখানে আমি উপাদানটির সূচক (0-সূচকযুক্ত) এবং শুরুর মান দেওয়া হয়।
অ্যারের সমস্ত উপাদানগুলির বিটওয়াইজ এক্সওর ফিরে আসতে হবে।

উদাহরণ

n = 4, start = 3
8

ব্যাখ্যা:

অ্যারের সংখ্যাগুলি [3, 5, 7, 9] এর সমান যেখানে (3 ^ 5 ^ 7 ^ 9) = 8।
যেখানে "^" বিটওয়াইজ এক্সওআর অপারেটরের সাথে সম্পর্কিত।

n = 1, start = 7
7

ব্যাখ্যা:

অ্যারের সংখ্যাগুলি [7] এর সমান, সুতরাং xor = 7।

পন্থা (ব্রুট ফোর্স)

আমরা কেবলমাত্র i = 0 থেকে i = n-1 এর জন্য লুপ n এর জন্য একটি চালাতে পারি। লুপের জন্য আমরা বর্তমান xor এর সাথে বিটওয়াইজ জোর (স্টার্ট + 2 * আই) করব যা আমরা একটি পরিবর্তনশীল রেজিসে সংরক্ষণ করব।

অ্যালগরিদম

1. অ্যারের উপাদানের সূচক উপস্থাপন করতে একটি ভেরিয়েবল ইন্ড তৈরি করুন এবং 0 দিয়ে সূচনা করুন।
2. লুপের সময় চলতি জোরটি সংরক্ষণ করার জন্য একটি পরিবর্তনশীল রেস তৈরি করুন এবং 0 দিয়ে আরম্ভ করুন।
3. ind = 0 থেকে ind = n-1 এ লুপের জন্য একটি চালান।
৪. রেট এর বিটওয়াইজ এক্সওর করুন (সূচনা + ২ * i) অর্থ সূচক ইন্ডে এলিমেন্ট এবং ফলাফলকে রেজিসে সংরক্ষণ করুন।
৫. রিসেসটি ফিরিয়ে দিন।

অ্যারের লেটকোড সলিউশনে XOR অপারেশনের জন্য বাস্তবায়ন

সি ++ প্রোগ্রাম

#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

একটি অ্যারে লেটকোড সমাধানে এক্সওআর অপারেশনের জন্য জটিলতা বিশ্লেষণ

সময় জটিলতা

চালু):  যেখানে এন হল অ্যারের প্রদত্ত আকার size যেহেতু আমরা N উপাদানের জন্য লুপের জন্য একক মধ্যে অ্যারেটি অতিক্রম করছি। সুতরাং সময়ের জটিলতা হ'ল ও (এন)।

স্পেস জটিলতা ity 

ও (1):  যেহেতু আমরা কিছু ভেরিয়েবল ব্যতীত কোনও অতিরিক্ত মেমরি ব্যবহার করছি না। অতএব অতিরিক্ত স্থান ব্যবহৃত ধ্রুবক।

পন্থা (বিট ম্যানিপুলেশন)

উপরের সমস্যাটিতে আমরা দেখতে পাচ্ছি যে প্রতিটি পরের উপাদানটির মধ্যে পার্থক্য ২। এর অর্থ হয় সমস্ত উপাদান সমান হবে বা সমস্ত বিজোড় হবে। এটি এক ধরণের রেঞ্জ তৈরি করে তবে একটানা নয় বরং এর বিকল্প মান রয়েছে।

বিট ম্যানিপুলেশন ব্যবহার করে আমরা ধ্রুবক সময়ে ক্রমাগত উপাদান থাকা একটি ব্যাপ্তির বিটওয়াইজ জোর খুঁজে পেতে পারি। আসুন কীভাবে দেখুন এবং তারপরে আমরা উপরের সমস্যাটিকে নীচের সমস্যায় রূপান্তরিত করার চেষ্টা করব:

ধরা যাক একটি পরিসীমা = [3,4,5,6,7,8,9,10], এবং আমাদের প্রথম এবং শেষ উপাদানটির মধ্যে সীমার মধ্যে xor প্রয়োগ করতে হবে।

X এর যেকোন সমান সংখ্যা এবং yie xie y = x + 1 এর পরের নম্বর হোক। আমরা সহজেই বিশ্লেষণ করতে পারি যে x এবং y এর xor সর্বদা 1. থাকবে বা তার পরে প্রতিটি সংখ্যার xor এবং এর পরে বিজোড় সংখ্যাটি সর্বদা 1. তাই আমরা উপসংহারে পৌঁছাতে পারি যে প্রথম এবং শেষ সংখ্যার মধ্যে প্রতিটি সম-বিজোড় জোড়া জোরের সমানকে দেয় ঘ।
i.e.   4^5=1,  6^7=1,  8^9=1

এখন যদি এই জোড়গুলির সংখ্যাটি বিজোড় হয় তবে 1 ম সমান সংখ্যা এবং শেষ বিজোড় সংখ্যাটির মধ্যে মৌলগুলির সংখ্যা 1 বা অন্য 0 হবে।
অর্থাত্ 4 ^ 5 ^ 6 ^ 7 ^ 8 ^ 9 = 1 ^ 1 ^ 1 = 1

এখন আমরা কেবলমাত্র শেষ পজিশনে সংখ্যাগুলি রেখেছি যা 3 এবং 10. সুতরাং আমাদের উত্তরটি 3 ^ 1 ^ 10 = 8 হবে নীচের চিত্রের মতো:

অ্যারে লেটকোড সলিউশনে এক্সওআর অপারেশন

একটানা পরিসীমা XOR এ সমস্যা রূপান্তর করা

উপরের সমস্যায় আমরা প্রতিটি উপাদানগুলির মধ্যে দূরত্ব 2 থেকে 1 কমাতে পারি যদি আমরা করি ডান শিফট বিটওয়াইজ প্রতিটি উপাদান 1 দ্বারা (2 দ্বারা বিভাজক হিসাবে সমান)। এটি করে আমরা কেবলমাত্র উপাদানগুলির শেষ বিটকে প্রভাবিত করছি। সুতরাং আমরা প্রথমে নিম্নলিখিত উত্তরগুলির দ্বারা আমাদের উত্তরগুলির শেষ বিটটি সংরক্ষণ করি:

1. যদি অ্যারেতে সমস্ত উপাদান বিজোড় হয় এবং মোট উপাদানের সংখ্যাও বিজোড় হয় তবে লাস্টবিট = 1।
2. অন্য লাস্টবিট = 0।

এখন আমরা প্রতিটি উপাদানকে 1 দ্বারা রাইট করার পরে, আমাদের পরিসীমাটি হয়ে যায়:

শুরু / 2, শুরু / 2 +1, শুরু / 2 +2,। । । । , শুরু / 2 + (এন -1)।

যেখানে প্রথম = শুরু / 2 এবং শেষ = শুরু / 2 + (এন -1)।

এখন আমরা সহজেই শেষ উপাদানগুলির বিটওয়াইজ জোর এবং অবিচ্ছিন্ন সময়ে তাদের মধ্যে সমস্ত সম-বিজোড় জোড়গুলি খুঁজে সহজেই এই ব্যাপ্তির জোরটি খুঁজে পেতে পারি।

জোর খুঁজে পাওয়ার পরে আমাদের যেতে হবে বিটওয়াইজ বাম শিফ্ট 1 দ্বারা ফলাফল আমাদের চূড়ান্ত উত্তরে বিটগুলির আসল অবস্থান অর্জন করতে। পরিশেষে শেষের দিকে ফলাফলটি যুক্ত করুন এবং এটি ফিরিয়ে দিন।

অ্যারের লেটকোড সলিউশনে XOR অপারেশনের জন্য বাস্তবায়ন

সি ++ প্রোগ্রাম

#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

একটি অ্যারে লেটকোড সমাধানে এক্সওআর অপারেশনের জন্য জটিলতা বিশ্লেষণ

সময় জটিলতা

ও (1):  যেহেতু আমরা অ্যারের সমস্ত উপাদানগুলির উপরে নজর রাখছি না, বিট ম্যানিপুলেশন ব্যবহার করে আমরা স্থির সময়ে এটি করেছি।

স্পেস জটিলতা ity 

ও (1):  এখানে অতিরিক্ত মেমরি ব্যবহৃত ধ্রুবক।