Time complexity for the array related problem

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.

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.

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.

MY SOLUTION

My solution fails at these scenarios, I am willing from SO community to please guide me how to think this problem so that i can overcome these failures

class Solution {
    public int solution(int[] A) {
       int[] result = new int[(int) Math.ceil((double)A.length/2)];
       for(int x = 0 ; x < result.length ; x++ ){
           result[x] = -1;
       }
       for(int x = 0 ; x < A.length ; x++ ){
           for(int y = 0 ; y < result.length ; y++){
               if(result[y] > -1  && result[y]== A[x])
               {
                   result[y] = -2;
                   break;
               }
               if(result[y] == -1 )
               {
                   result[y] = A[x];
                   break;
               }
           }
       }

       for(int x = 0 ; x < result.length ; x++ ){
           if(result[x] > -1){
           return result[x];
           }
       }
       return -1;
    }
}

FAILURES

medium random test n=100,003 Killed. Hard limit reached: 7.000 sec.

big random test n=999,999, multiple repetitions Killed. Hard limit reached: 14.000 sec.

big random test n=999,999 Killed. Hard limit reached: 19.000 sec.

Since the large input is of size 1000000, you have to think how to solve it in linear or at worst O(n log n) time. Generally programming website problems have O(n^2) solutions only if the largest test cases have size around 1000. — Paul Hankin
– Paul Hankin, Commented May 12, 2020 at 14:51

Dave · Accepted Answer · 2020-05-13 01:04:39Z

5

If it is guaranteed that the input has only one unpaired element, it is very simple to identify it by doing an XOR of all elements.

int x = A[0];
for ( int i = 1; i < A.length; i++ )
     x = x ^ A[i];

The resulting value is the one which is not paired.

Example:

public static void main (String[] args) throws java.lang.Exception
    {
        int[] A = {9, 3, 9, 2, 4, 2, 4, 7, 3};
        int x = A[0];
        for ( int i = 1; i < A.length; i++ )
            x = x ^ A[i];
        System.out.println(x);
    }

Output is 7.

Time complexity is O(n)

This works because the XOR of a number with itself is zero.

edited May 13, 2020 at 1:04

Dave

9,1503 gold badges30 silver badges44 bronze badges

answered May 12, 2020 at 14:33

SomeDude

14.3k5 gold badges26 silver badges49 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

MBo · Accepted Answer · 2020-05-12 14:42:42Z

2

The most effective solution exploits interesting property of bitwise XOR operation:

a xor a = 0

for any value of a, so xor'ing all array items just gives unpaired value

public int solution(int[] A) {
   int result = 0;
   for(int x = 0 ; x < A.length ; x++ )
       result ^= A[x];
   return result;
}

edited May 12, 2020 at 14:42

answered May 12, 2020 at 14:34

MBo

80.7k5 gold badges61 silver badges98 bronze badges

Collectives™ on Stack Overflow

Time complexity for the array related problem

2 Answers 2

Comments

Comments

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Related