Ttdfjt

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.

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

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

Minor comments

• Do not start your variable names with a capital letter (A). This convention is reserved for classes.

Edit

Now it came to my mind that you can solve this task with one passage (in O(N)) without an additional array.