Аперацыя XOR у масіве Leetcode Solution


Узровень складанасці Лёгка
Часта пытаюцца ў Лабараторыі Walmart
масіў Бітавая маніпуляцыя біты Разрадна-XOR

Пастаноўка праблемы

У гэтай задачы мы павінны зрабіць аперацыю XOR у масіве памерам n, у якім кожны элемент роўны (start + 2 * i), дзе i - індэкс элемента (0-індэксаваны) і дадзена значэнне старту.
Мы павінны вярнуць разрадны XOR усіх элементаў масіва.

Прыклад

n = 4, start = 3
8

Тлумачэнне:

Нумары масіваў роўныя [3, 5, 7, 9], дзе (3 ^ 5 ^ 7 ^ 9) = 8.
Дзе "^" адпавядае разраднаму аператару XOR.

n = 1, start = 7
7

Тлумачэнне:

Нумары масіваў роўныя [7], адсюль xor = 7.

Падыход (грубая сіла)

Мы можам проста запусціць цыкл for n раз пры i = 0 да i = n-1. У цыкле for мы будзем рабіць па разрадзе xor (start + 2 * i) з бягучым xor, які мы будзем захоўваць у зменнай res.

Алгарытм

1. стварыць зменную ind для прадстаўлення індэкса элемента масіва і ініцыялізаваць з 0.
2. стварыць зменную res для захоўвання бягучага xor падчас цыкла for і ініцыялізаваць 0.
3. Запусціце цыкл for з ind = 0 на ind = n-1.
4. Зрабіце разраднае xor з res з (start + 2 * i), г.зн. элемент з індэксам ind і захавайце вынік у 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

Праграма Java

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 - дадзены памер масіва. Паколькі мы перамяшчаем масіў у адзіны цыкл for для N элементаў. Такім чынам, складанасць часу складае O (N).

Касмічная складанасць 

O (1):  Паколькі мы не выкарыстоўваем дадатковай памяці, акрамя некаторых зменных. Такім чынам, дадатковае выкарыстанае месца з'яўляецца пастаянным.

Падыход (Бітавая маніпуляцыя)

У прыведзенай вышэй праблеме мы бачым, што розніца паміж кожным наступным элементам роўная 2. Гэта азначае, што альбо ўсе элементы будуць цотнымі, альбо ўсе будуць няцотнымі. Гэта робіць свайго роду дыяпазон, але не паслядоўны, гэта значыць ён мае альтэрнатыўныя значэнні.

Выкарыстоўваючы бітавыя маніпуляцыі, мы можам знайсці разраднае xor дыяпазону, які мае паслядоўныя элементы ў ім у пастаянны час. Давайце паглядзім, як, а потым паспрабуем пераўтварыць вышэйзгаданую праблему ў праблему ніжэй:

Дапусцім, дыяпазон = [3,4,5,6,7,8,9,10], і мы павінны прымяніць 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, а то 0.
г.зн. 4 ^ 5 ^ 6 ^ 7 ^ 8 ^ 9 = 1 ^ 1 ^ 1 = 1

Цяпер нам засталіся толькі лічбы ў канчатковых пазіцыях, якія роўныя 3 і 10. Такім чынам, наш адказ будзе 3 ^ 1 ^ 10 = 8, як паказана на малюнку ніжэй:

Аперацыя XOR у масіве Leetcode Solution

Пераўтварэнне праблемы ў паслядоўны дыяпазон XOR

У прыведзенай вышэй праблеме мы можам паменшыць адлегласць паміж кожным элементам з 2 да 1 зрух па разрадзе направа кожны элемент на 1 (тое ж самае, што і дзяленне на 2). Робячы гэта, мы ўплываем толькі на апошні біт элементаў. Такім чынам, мы спачатку захоўваем апошні біт нашага анса, наступныя выпадкі:

1. Калі ўсе элементы ў масіве няцотныя і агульная колькасць элементаў таксама няцотная, то lastbit = 1.
2. У астатнім lastbit = 0.

Цяпер, калі мы зрушылі кожны элемент направа на 1, наш дыяпазон становіцца:

start / 2, start / 2 +1, start / 2 +2,. . . . , start / 2 + (n-1).

Дзе першы = старт / 2 і апошні = старт / 2 + (n-1).

Цяпер мы можам лёгка высветліць xor гэтага дыяпазону, знайшоўшы разраднае xor канцавых элементаў і ўсіх цотных няцотных пар паміж імі ў пастаянны час.

Пасля пошуку xor мы павінны разраднае зрушэнне ўлева вынік на 1, каб атрымаць канчатковае становішча біт у нашым канчатковым адказе. Нарэшце дадаць lastbit да выніку і вярнуць яго.

Рэалізацыя аперацыі 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

Праграма Java

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):  Тут таксама выкарыстоўваецца дадатковая памяць сталая.