Codility Lesson2 - OddOccurrencesInArray

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.

N개의 정수로 구성된 비어 있지 않은 배열 A가 제공됩니다. 배열에는 홀수 개의 요소가 포함되며, 배열의 각 요소는 짝을 이루지 않은 상태로 있는 한 개의 요소를 제외하고는 동일한 값을 가진 다른 요소와 쌍을 이룰 수 있습니다.

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.

인덱스 0과 2의 요소는 값 9를 가집니다,
인덱스 1과 3의 요소는 값 3을 가집니다,
인덱스 4와 6의 요소는 값 9를 가집니다,
인덱스 5의 원소는 값 7을 가지며 짝을 이루지 않습니다.

Write a function:

class Solution { public int solution(int[] A); }

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

위의 조건을 만족하는 N개의 정수로 구성된 배열 A가 주어지면 짝을 이루지 않은 요소의 값을 반환합니다.

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.

위의 예제에서 설명한 바와 같이 함수가 7을 반환해야 합니다.

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.

N은 [1..1,000,000] 범위 내의 홀수 정수입니다;
배열 A의 각 요소는 [1..1,000,000,000,000] 범위 내의 정수입니다;
A의 값 중 하나를 제외한 모든 값은 짝수 번 발생합니다.

---

2023.08.08

class Solution {
    public int solution(int[] A) {
        int answer = 0;
        int index = 0;

        while(index < A.length) {
            if(A[index] > -1) {
                for(int i = index + 1; i < A.length; i++) {
                    if(A[index] == A[i]) {
                        A[i] = -1;
                        A[index] = -1;
                    }
                }
                if(A[index] > -1) {
                    return A[index];
                }
            }
            index++;
        }

        return answer;
    }
}

 - Timeout

class Solution {
    public int solution(int[] A) {
        int answer = 0;

        for(int i = 0; i < A.length; i++) {
            answer = answer ^ A[i];
        }

        return answer;
    }
}

같은 값이 짝수로 존재하기 때문에 비트연산(XOR) 시 홀수로 존재하는 한 개의 값이 남게 됨.