어레이 Leetcode 솔루션의 XOR 연산


난이도 쉽게
자주 묻는 질문 월마트 연구소
배열 비트 조작 비트 비트 XOR

문제 정책

이 문제에서 우리는 각 요소가 (start + 2 * i)와 같은 크기 n의 배열에서 XOR 연산을해야합니다.
배열의 모든 요소의 비트 별 XOR을 반환해야합니다.

n = 4, start = 3
8

설명 :

배열 번호는 [3, 5, 7, 9]와 같습니다. 여기서 (3 ^ 5 ^ 7 ^ 9) = 8입니다.
여기서“^”는 비트 XOR 연산자에 해당합니다.

n = 1, start = 7
7

설명 :

배열 nums는 [7]이므로 xor = 7입니다.

접근 (Brute Force)

i = 0에서 i = n-1까지 for 루프를 n 번 실행하면됩니다. for 루프에서 우리는 변수 res에 저장할 현재 xor로 (start + 2 * i)의 비트 xor를 수행 할 것입니다.

암호알고리즘

1. 배열 요소의 인덱스를 나타내는 변수 ind를 만들고 0으로 초기화합니다.
2. for 루프 동안 현재 xor를 저장할 변수 res를 만들고 0으로 초기화합니다.
3. ind = 0에서 ind = n-1까지 for 루프를 실행합니다.
4. (start + 2 * i) 즉, 인덱스 ind의 요소로 res의 비트 xor를 수행하고 결과를 res에 저장합니다.
5. res를 반환합니다.

어레이 Leetcode 솔루션에서 XOR 작동을위한 구현

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

어레이 Leetcode 솔루션에서 XOR 연산을위한 복잡성 분석

시간 복잡성

의 위에):  여기서 N은 주어진 배열 크기입니다. N 개의 요소에 대해 단일 for 루프에서 배열을 순회하고 있습니다. 따라서 시간 복잡도는 O (N)입니다.

공간 복잡성 

O (1) :  일부 변수 이외의 추가 메모리를 사용하지 않기 때문입니다. 따라서 사용되는 추가 공간은 일정합니다.

접근하다 (비트 조작)

위의 문제에서 우리는 각 다음 요소의 차이가 2임을 알 수 있습니다. 이는 모든 요소가 짝수이거나 모두 홀수임을 의미합니다. 그것은 일종의 범위를 만들지 만 연속적이지는 않습니다. 즉 대체 값을 가지고 있습니다.

비트 조작을 사용하여 일정한 시간에 연속 요소가있는 범위의 비트 xor를 찾을 수 있습니다. 방법을 살펴본 다음 위의 문제를 아래 문제로 변환 해 보겠습니다.

범위 = [3,4,5,6,7,8,9,10]을 가정하고 첫 번째 요소와 마지막 요소 사이의 범위에 xor를 적용해야합니다.

x는 짝수이고 y는 xie y = x + 1 옆의 숫자라고합시다. x와 y의 xor는 항상 1이된다는 것을 쉽게 분석 할 수 있습니다. 또는 모든 짝수와 그 옆의 홀수의 xor는 항상 1입니다. 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이됩니다.

어레이 Leetcode 솔루션의 XOR 연산

문제를 연속 범위 XOR로 변환

위의 문제에서 우리는 각 요소 사이의 거리를 2에서 1로 줄일 수 있습니다. 비트 단위로 오른쪽 시프트 각 요소는 1로 나눈다 (2로 나누는 것과 동일). 이렇게하면 요소의 마지막 부분에만 영향을줍니다. 따라서 먼저 다음과 같은 경우에 따라 ans의 마지막 비트를 저장합니다.

1. 배열의 모든 요소가 홀수이고 총 요소 수도 홀수이면 lastbit = 1입니다.
2. 그렇지 않으면 lastbit = 0.

이제 각 요소를 1만큼 오른쪽으로 이동하면 범위는 다음과 같습니다.

시작 / 2, 시작 / 2 +1, 시작 / 2 +2,. . . . , 시작 / 2 + (n-1).

여기서 처음은 시작 / 2이고 마지막은 시작 / 2 + (n-1)입니다.

이제 우리는 끝 요소의 비트 xor와 그 사이의 모든 짝수-홀수 쌍을 일정한 시간에 찾아이 범위의 xor를 쉽게 찾을 수 있습니다.

xor를 찾은 후에는 비트 왼쪽 시프트 최종 답변에서 비트의 원래 위치를 얻기 위해 결과를 1만큼 얻습니다. 마지막으로 결과에 lastbit를 추가하고 반환합니다.

어레이 Leetcode 솔루션에서 XOR 작동을위한 구현

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

어레이 Leetcode 솔루션에서 XOR 연산을위한 복잡성 분석

시간 복잡성

O (1) :  배열의 모든 요소를 ​​순회하지 않기 때문에 비트 조작을 사용하여 일정한 시간에 수행했습니다.

공간 복잡성 

O (1) :  여기서도 사용되는 추가 메모리는 일정합니다.