'Odd Occurences In Array'에 해당되는 글 1건

  1. 2020.02.25 [Lesson 02_2] Odd Occurences In Array
1일 1코딜리티2020. 2. 25. 17:09
728x90

Answer

// you can use includes, for example:
// #include <algorithm>

// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;

int solution(vector<int> &A) {
    // write your code in C++14 (g++ 6.2.0)
    int key=0;
    for(int i=0; i<A.size(); i++){
        key ^= A[i];
    }
    return key;
}

 

Solution Point :

이 문제의 해결 포인트는 다음과 같다.

array A의 모든 원소XOR 했을 때, 홀수개 인 수만 남는다.

 

XOR 테이블

입력 출력
A B F
0 0 0
0 1 1
1 0 1
1 1 0

XOR은 두 수가 같을 경우 0을 출력하고, 다를 경우 1을 출력한다.

즉, 동일 한 수가 두 번 나올 경우 XOR값은 0이 된다.

 

문제에 나온 예시인

9 ⊕ 3 ⊕ 9 ⊕ 3 ⊕ 9 ⊕ 7 ⊕ 9

= 1001 ⊕ 0011 ⊕ 1001 ⊕ 0011 ⊕ 1001 ⊕ 0111 ⊕ 1001

= 0111(2진수) = 7(10진수)

 

첫째자리 : 1 0 1 0 1 0 1 -> 1이 짝수개 -> 0

둘째자리 : 0 0 0 0 0 1 0 -> 1이 홀수개 -> 1

셋째자리 : 0 1 0 1 0 1 0 -> 1이 홀수개 -> 1

넷째자리 : 1 1 1 1 1 1 1 -> 1이 홀수개 -> 1

따라서 결과가 0111 즉, 7로 하나만 있는 수가 나오게 된다.

 

 

반응형

'1일 1코딜리티' 카테고리의 다른 글

[ Lesson 04_1 ] FrogRiverOne  (0) 2020.03.01
[ lesson 03_3 ] TapeEquilibrium  (0) 2020.02.27
[ Lesson 03_2 ] PermMissingElem  (0) 2020.02.27
[ Lesson 03 ] FrogJmp  (0) 2020.02.26
코딜리티(Codility) 사이트  (0) 2020.01.08
Posted by mminky