Codility 2-2 OddOccurrencesInArray
A non-empty zero-indexed 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:
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.
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.
Assume that:
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. Complexity:
expected worst-case time complexity is O(N); expected worst-case space complexity is O(1), beyond input storage (not counting the storage required for input arguments).
이 문제는 어떻게 풀지 고민했는데. 예전에는 Set, Map에 넣어서 중복 여부를 체크하고 중복되지 않은 값을 리턴했던거 같은데... 이번에 어쩌다 보니까 비트 연산을 사용해서 풀게 됐다.
XOR 연산을 사용할 생각도 못 했는데 지나가다 어떤 컴퓨터같은 사람이 쓴 코드를 보고 문득 생각이 들어서 XOR을 이용해 풀어봤는데 잘 작동한다.
XOR 연산은 두 값의 각 자릿수를 비교해,값이 0으로 같으면 0, 값이 1로 같으면 0, 다르면 1을 계산한다.
0101
XOR 0011
= 0110
그러니까, 3, 4, 4가 있다고 하면 011, 100 100의 이진법 값이 있을테고 3개를 연속적으로 연산한다고 해보자.
두 자릿수가 같으면 0, 다르면 1이 된다. 결국 011 ^ 100 = 111이 되고 111 ^ 100 = 011이 되어서 다시 3이 된다.
결국 100 ^ 100 = 000이 되고 다른 모든 같은 쌍의 값들의 경우에도 000이 되어서 000 ^ 011 = 011이 되어서 하나 다른 3의 값만이 남게 된다. 그래서 위와 같은 경우의 문제에서 result ^= A[i]를 하면 result에는 다른 하나의 값만이 나와서 정답이 나오게 된다.
import java.util.*;
class Solution {
public int solution(int[] A) {
return Arrays.stream(A).reduce((a, b) -> a^= b).getAsInt();
}
}