# Finding unpaired number in an odd length Array of integers

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:
 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.

class Solution {

public int solution(int[] A) {

final int len = A.length;

Arrays.sort(A);

for (int i = 0; i < len ;) {
int counter = 1;
int current = A[i];

while ((i < len - 1) && (current == A[++i])) {
counter++;
}

if (counter % 2 == 1) {
return current;
}
}
return -1;
}
}


Could this code be bettered in terms of time complexity or code quality?

Sorting of the array will take O(n (log n)) in the average case. You can do it in linear time using bitwise operation

public class Test {
public static void main(){
int a = 0;
int[] arr = {9,3,9,3,9,7,9};

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

System.out.println(a);
}
}


Any number which will XOR with 0 will be the number itself. But if it will XOR with itself, it will be 0. In the end, we'll get the non paired number.

• Nice. One drawback is that this method will always return a result, even if the array is empty, if it contains no single integer or if it contains multiple unpaired int. Jul 20 '19 at 8:13
• It's possible to use a stream and reduce for a relatively clean one-liner. As a bonus, it fails with an empty array. Jul 20 '19 at 8:24
• @EricDuminil, Here are the requirements from the original question - "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". Moreover, we don't need to run the loop if the array is empty. Easy to code a one-line condition. Jul 22 '19 at 22:18
• sure, the above specs say so. It doesn't hurt to try to make the method more reliable, though. Jul 23 '19 at 5:06
• Regarding time complexity. If you use an additional array, you can make only one passage through the array (not doing sorting) and have time complexity O(N), where N - the number of elements in the array. Currently, it's O(NlogN) because of sorting.

• Currently looks like if your method returns -1, it means that you have an even number of elements in the array (Invalid input?) So maybe you should throw some Exception such as IllegalArgumentException in this case? Moreover, what if you have elements with value -1 in your array?

• You should simplify your loops. You have nested loop structure, however, you can have only one since you traverse the array only once. Currently, because of 2 loop structures, it takes some time to understand what's going on, where you increment your i variable, what is the stop condition, etc.

• Do not start your variable names with a capital letter (A). This convention is reserved for classes.
Now it came to my mind that you can solve this task with one passage (in O(N)) without an additional array.
• [using] an additional array, you can make only one passage through the array (not doing sorting) and have time complexity O(N) care to sketch how (other than the cancellation approach mentioned in Vikas' answer?) Nov 14 '19 at 9:56