어레이 Leetcode 솔루션의 XOR 연산

난이도 쉽게
자주 묻는 질문 월마트 연구소
알고리즘 배열 비트 조작 비트 비트 XOR 코딩 인터뷰 인터뷰 준비 리트코드 LeetCodeSolutions조회수 88

시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.

문제 정책

이 문제에서 우리는 각 요소가 (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) :  여기서도 사용되는 추가 메모리는 일정합니다.

균열 시스템 설계 인터뷰
Translate »