Операция XOR в решении Leetcode с массивом


Сложный уровень Легко
Часто спрашивают в Walmart Labs
массив Битовые манипуляции Биты Побитовое исключающее ИЛИ

Постановка задачи

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

Пример

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 of (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. Вернуть res.

Реализация операции XOR в решении 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

Программа 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 для массива

Сложность времени

НА):  Где N - заданный размер массива. Поскольку мы обходим массив в одном цикле for для N элементов. Следовательно, временная сложность O (N).

Космическая сложность 

О (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 с массивом

Преобразование проблемы в последовательный диапазон XOR

В приведенной выше задаче мы можем уменьшить расстояние между каждым элементом с 2 до 1, если мы побитовый сдвиг вправо каждый элемент на 1 (аналогично делению на 2). Делая это, мы затрагиваем только последнюю часть элементов. Итак, сначала мы сохраняем последний бит нашего ответа в следующих случаях:

1. Если все элементы в массиве нечетные и общее количество элементов также нечетное, то lastbit = 1.
2. Остальной lastbit = 0.

Теперь, после того как мы сдвинем каждый элемент вправо на 1, наш диапазон станет:

старт / 2, старт / 2 +1, старт / 2 +2,. . . . , старт / 2 + (n-1).

Где first = start / 2 и last = start / 2 + (n-1).

Теперь мы можем легко узнать xor этого диапазона, найдя побитовое xor конечных элементов и всех четно-нечетных пар между ними за постоянное время.

После нахождения xor мы должны побитовый сдвиг влево результат на 1, чтобы получить исходное положение битов в нашем окончательном ответе. Наконец, добавьте последний бит к результату и верните его.

Реализация операции XOR в решении 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

Программа 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 для массива

Сложность времени

О (1):  Поскольку мы не обходим все элементы массива, используя битовые манипуляции, мы сделали это за постоянное время.

Космическая сложность 

О (1):  Здесь также используется постоянная дополнительная память.