3
\$\begingroup\$

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?

\$\endgroup\$
3
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – Eric Duminil Jul 20 at 8:13
  • \$\begingroup\$ It's possible to use a stream and reduce for a relatively clean one-liner. As a bonus, it fails with an empty array. \$\endgroup\$ – Eric Duminil Jul 20 at 8:24
  • \$\begingroup\$ @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. \$\endgroup\$ – Vikas Jul 22 at 22:18
  • \$\begingroup\$ sure, the above specs say so. It doesn't hurt to try to make the method more reliable, though. \$\endgroup\$ – Eric Duminil Jul 23 at 5:06
3
\$\begingroup\$
  • 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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.