[Codility] Lesson2 - Arrays: Odd Occurrences In Array (c++)

Problem

A non-empty array A consisting of N integers is given. The array contains an odd number of elements, and each element of the array can be paired with another element that has the same value, except for one element that is left unpaired.

For example, in array A such that:

A[0] = 9 A[1] = 3 A[2] = 9 A[3] = 3 A[4] = 9 A[5] = 7 A[6] = 9

• the elements at indexes 0 and 2 have value 9,
• the elements at indexes 1 and 3 have value 3,
• the elements at indexes 4 and 6 have value 9,
• the element at index 5 has value 7 and is unpaired.

Write a function:

int solution(vector<int> &A);

that, given an array A consisting of N integers fulfilling the above conditions, returns the value of the unpaired element.

For example, given array A such that:

A[0] = 9 A[1] = 3 A[2] = 9 A[3] = 3 A[4] = 9 A[5] = 7 A[6] = 9

the function should return 7, as explained in the example above.

Write an efficient algorithm for the following assumptions:

• N is an odd integer within the range [1..1,000,000];
• each element of array A is an integer within the range [1..1,000,000,000];
• all but one of the values in A occur an even number of times.

How to solve

- 정보

배열 A에 N개의 홀수로 이루어진 정수가 주어짐

각 원소는 다른 원소와 같은 값끼리 쌍을 맺음 (1개는 unpair)

 

- 구해야 하는것?

unpair된 원소 return!

 

 

- 풀이

sol1.

map을 생성해서, A배열의 갯수만큼 for문을 돌면서 map에 원소들을 넣는다

map에 원소가 없다면, map.insert(원소, 1)

map에 이미 원소가 있다면, map의 기존 원소의 갯수에 +1 해준다

 

map의 처음부터 끝까지 순회하면서 원소의 갯수가 홀수개인 원소를 return 한다

 

결과는 timeout!!!! ㅠㅠㅠ

sol2.

map -> unordered_map 사용했더니 time out이 나지 않았어요!

map은 트리맵 구조이고, unordered_map은 해시맵 구조라서 그렇다고 하네요

친구가 설명해줬습니다 ㅎㅎ

고마운 마틴님!

 

sol3.

sort를 이용하여 우선 정렬

sort를 이용하여 정렬하고 i를 2만큼 증가시켜가며,

i, i+1번째 원소를 비교해서

다르면 i번째 원소 return

마지막 원소가 답일경우 마지막 원소 return

Solution(c++)

sol1. map 사용 - timeout난 코드 ㅠㅠ

// you can use includes, for example:
#include <bits/stdc++.h>

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

int solution(vector<int> &A) {
    // write your code in C++14 (g++ 6.2.0)
    map<int, int> m1;
    map<int, int>::iterator iter;

    for(int i=0; i<A.size(); i++){
        //map에 없으면 map에 넣기
        if(m1.find(A[i]) == m1.end()){
            m1.insert({A[i], 1});
        }else{
            m1[A[i]] += 1;
        }
    }

    for(iter=m1.begin(); iter!=m1.end(); iter++){
        if(iter->second %2 == 1){
            return iter->first;
        }
    }
}

 

app.codility.com/demo/results/trainingB5WM8U-M3C/

Test results - Codility

sol2. unordered_map 사용

// you can use includes, for example:
#include <bits/stdc++.h>

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

int solution(vector<int> &A) {
    // write your code in C++14 (g++ 6.2.0)
    unordered_map<int, int> m1;
    unordered_map<int, int>::iterator iter;

    for(int i=0; i<A.size(); i++){
        //map에 없으면 map에 넣기
        if(m1.find(A[i]) == m1.end()){
            m1.insert({A[i], 1});
        }else{
            m1[A[i]] += 1;
        }
    }

    for(iter=m1.begin(); iter!=m1.end(); iter++){
        if(iter->second %2 == 1){
            return iter->first;
        }
    }
}

app.codility.com/demo/results/trainingBQVP4G-P7B/

 

sol3. sort를 이용하여 우선 정렬

// you can use includes, for example:
#include <bits/stdc++.h>

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

using namespace std;

int solution(vector<int> &A) {
    // write your code in C++14 (g++ 6.2.0)
    
    // 원소갯수 1개
    if(A.size() == 1){
        return A[0];
    }
    // sort
    sort(A.begin(), A.end());
    
    // 
    for(int i=0; i<A.size(); i=i+2){
        //마지막꺼
        if(i+1 == A.size()){
            return A[i];
        }
        if(A[i] != A[i+1]){
            return A[i];
        }
    }
}

 

sol4. python 쩌는 답안!!!!!!!!!!!!!!!

2개의 수를 2진수로 바꿔 비교!!! 

x^y는 2진수로 바꾸었을 때 같으면 0 다르면 1을 return 

즉, 3 을 2진수로 하면 11,

3과 3을 XOR연산을 하면 0이 나온다

 

python의 reduce함수는 연산값을 누적하여 return하는 함수

즉, 모든 원소를 XOR해서 다 더하면 짝이없는 원소만 return 됨!!!!!!!!!!!!!!

 

세상 대단하신분..

코드 설명해준 마틴님 감사합니다 ㅎㅎ

 

wayhome25.github.io/algorithm/2017/04/30/OddOccurrencesInArray/

def solution(A):
	return reduce(lambda x,y: x^y, A)