عملية XOR في حل Array Leetcode


مستوى الصعوبة سهل
كثيرا ما يطلب في مختبرات وول مارت
مجموعة معالجة البت بت Bitwise-XOR

المشكلة بيان

في هذه المشكلة ، يتعين علينا إجراء عملية XOR في مصفوفة بالحجم n حيث يكون كل عنصر مساويًا لـ (start + 2 * i) حيث i هو فهرس العنصر (مفهرس 0) ويتم إعطاء قيمة البداية.
يتعين علينا إرجاع 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 n مرة من أجل i = 0 إلى i = n-1. في حلقة for سنفعل xor أحاديًا لـ (start + 2 * i) مع xor الحالي الذي سنخزنه في متغير الدقة.

خوارزمية

1. قم بإنشاء متغير ind لتمثيل فهرس عنصر المصفوفة وتهيئة بـ 0.
2. إنشاء متغير الدقة لتخزين xor الحالي أثناء حلقة for وتهيئة بـ 0.
3. قم بتشغيل حلقة for من ind = 0 إلى ind = n-1.
4. قم بعمل xor للبت باستخدام (start + 2 * i) أي عنصر في index ind وقم بتخزين النتيجة في res.
5. إعادة الدقة.

تنفيذ عملية XOR في حل Array Leetcode

برنامج 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 في حل Array Leetcode

تعقيد الوقت

على):  حيث N هو الحجم المعطى للصفيف. نظرًا لأننا نجتاز المصفوفة في حلقة for واحدة لعناصر N. ومن ثم فإن التعقيد الزمني هو O (N).

تعقيد الفضاء 

يا (1):  حيث أننا لا نستخدم أي ذاكرة إضافية بخلاف بعض المتغيرات. ومن ثم فإن المساحة الإضافية المستخدمة ثابتة.

مقاربة (معالجة البت)

في المسألة أعلاه يمكننا أن نرى أن الفرق بين كل عنصر تالي هو 2. وهذا يعني إما أن جميع العناصر ستكون زوجية أو كلها ستكون فردية. هذا يجعل نوعًا من النطاق ولكن ليس متتاليًا ، أي أنه يحتوي على قيم بديلة.

باستخدام معالجة البتات ، يمكننا إيجاد xor أحاديًا لنطاق به عناصر متتالية فيه في وقت ثابت. دعونا نرى كيف ، وبعد ذلك سنحاول تحويل المشكلة أعلاه إلى المشكلة أدناه:

لنفترض أن النطاق = [3,4,5,6,7,8,9,10،XNUMX،XNUMX،XNUMX،XNUMX،XNUMX،XNUMX،XNUMX] ، وعلينا تطبيق xor في النطاق بين العنصر الأول والأخير.

لنفترض أن x هو أي عدد زوجي وأن يكون y هو الرقم المجاور لـ xie y = x + 1. يمكننا بسهولة تحليل أن xor لـ x و y سيكونان دائمًا 1. أو xor لكل رقم زوجي ورقم فردي بجواره دائمًا 1. ومن ثم يمكننا أن نستنتج أن كل أزواج زوجية فردية بين الرقم الأول والأخير تعطي xor يساوي 1.
i.e.   4^5=1,  6^7=1,  8^9=1

الآن إذا كان عدد هذه الأزواج فرديًا ، فسيكون xor للعناصر بين أول رقم زوجي وآخر رقم فردي 1 ، وإلا سيكون 1.
أي 4 ^ 5 ^ 6 ^ 7 ^ 8 ^ 9 = 1 ^ 1 ^ 1 = 1

الآن لم يتبق لنا سوى الأرقام الموجودة في المواضع النهائية وهي 3 و 10. وبالتالي ستكون إجابتنا 3 ^ 1 ^ 10 = 8 كما هو موضح في الشكل أدناه:

عملية XOR في حل Array Leetcode

تحويل المشكلة إلى نطاق متتالي XOR

في المسألة أعلاه يمكننا تقليل المسافة بين كل عنصر من 2 إلى 1 إذا كنا التحول الصحيح باتجاه أحادي كل عنصر على 1 (مثل القسمة على 2). من خلال القيام بذلك ، فإننا نؤثر فقط على الجزء الأخير من العناصر. لذلك نقوم أولاً بتخزين الجزء الأخير من إجاباتنا من خلال الحالات التالية:

1. إذا كانت جميع العناصر في المصفوفة فردية وكان إجمالي عدد العناصر أيضًا فرديًا ، فإن lastbit = 1.
2. آخر بيت آخر = 0.

الآن بعد أن نحول كل عنصر بشكل صحيح بمقدار 1 ، يصبح نطاقنا:

ابدأ / 2 ، ابدأ / 2 +1 ، ابدأ / 2 +2 ،. . . . ، بدء / 2 + (n-1).

حيث الأول = البداية / 2 والأخير = البداية / 2 + (ن -1).

يمكننا الآن بسهولة إيجاد xor لهذا النطاق من خلال إيجاد xor أحاديًا لعناصر النهاية وجميع الأزواج الزوجية الفردية بينها في وقت ثابت.

بعد العثور على xor ، يتعين علينا ذلك تحول اليسار أحاديا النتيجة بمقدار 1 للحصول على الموضع الأصلي للبتات في إجابتنا النهائية. أخيرًا أضف البت الأخير إلى النتيجة وأعده.

تنفيذ عملية XOR في حل Array Leetcode

برنامج 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 في حل Array Leetcode

تعقيد الوقت

يا (1):  نظرًا لأننا لا نتخطى جميع عناصر المصفوفة ، باستخدام معالجة البتات ، فقد قمنا بذلك في وقت ثابت.

تعقيد الفضاء 

يا (1):  هنا أيضًا الذاكرة الإضافية المستخدمة ثابتة.