Sunday 15 April 2018

Find the element that appears once in an array

Given an array of integers. All the numbers, except one number repeated twice, and one number presented exactly once.

You need to find an element that appears only once.

Example 1
Input : [1, 2, 3, 4, 4, 3, 5, 2, 1]
Output : 5

Example 2
Input : [100, 6, 100]
Output : [6]

Approach 1:
Take first element of the array, and check all the other elements in array for the existence of this element, if no element is existed, return this element, else repeat this step with next element in the array.

ArrayUtil.java
package com.sample.arrays;

public class ArrayUtil {

    /**
   * In <code>arr</code>, all the numbers, except one number repeated twice, and
   * one number repeated only once. This method return the elements that is not
   * repeated.
   * 
   * @param arr
   * @return
   */
    public static int getUniqueElement(int arr[]) {
        if (arr == null) {
            throw new IllegalArgumentException("arrar couldn't be null");
        }

        boolean isEleRepeated;

        for (int i = 0; i < arr.length; i++) {
            isEleRepeated = false;
            for (int j = 0; j < arr.length; j++) {
                if (i == j)
                    continue;

                if (arr[i] == arr[j]) {
                    isEleRepeated = true;
                    break;
                }

            }

            if (!isEleRepeated) {
                return arr[i];
            }

        }

        throw new IllegalArgumentException("arr do not satisfy the input criteria");
    }
}

Time complexity: O(n*n)
Since we are comparing all the elements of arraya gainst all the elements of array, the time complexity is O(n*n), where n is number of elements in the array.

Space complexity: O(n)

Approach 2: Sort the elements of the array, and check the element with next element, whether they are equal or not. If those are not equal, then first element in the pair is the result.

For the input: [1, 2, 4, 4, 3, 5, 5, 2, 1]
After sorting the array looks like [1, 1, 2, 2, 3, 4, 4, 5, 5]

Now check the elements at indexes (0, 1), (2, 3), (4, 5)....(n-2, n-1) for equality. Whenever you found a pair with inequality, the first element in the pair is the uniquely existed element.

In the above example

(1, 1), (2, 2), (3, 4). third pair is not equal, so 3rd element is the result.
ArrayUtil.java
package com.sample.arrays;

import java.util.Arrays;

public class ArrayUtil {

    /**
   * In <code>arr</code>, all the numbers, except one number repeated twice, and
   * one number repeated only once. This method return the elements that is not
   * repeated.
   * 
   * @param arr
   * @return
   */
    public static int getUniqueElement(int arr[]) {
        if (arr == null || arr.length == 0) {
            throw new IllegalArgumentException("arrar couldn't be null");
        }

        Arrays.sort(arr);
        int n = arr.length;

        int i = 0;

        while (i < n - 1) {
            if (arr[i] == arr[i + 1]) {
                i += 2;
                continue;
            }

            return arr[i];
        }

        /* Unique element can exist as last element of the array */
        if (i == n - 1) {
            return arr[i];
        }

        throw new IllegalArgumentException("arr do not satisfy the input criteria");
    }
}

Time Complexity: O(n log n) + O(n) = o(n log n)
suppose 'n' represents number of elements in the array,
To sort the elements: O (n log n)
To find the element in worst case, we require n/2 comparisons: O (n/2) = O (n)
Total complexity = O(n log n) + O(n) = O(n log n)

Approach 3:
This is an enhancement to approach 2. Once the elements are sorted, we can use binary search logic to identify the element.

For example,
for the input [1, 2, 4, 4, 3, 5, 5, 2, 1, 6, 6, 8, 8]

After sorting elements look like below.
[1, 1, 2, 2, 3, 4, 4, 5, 5, 6, 6, 8, 8]

As you see, elements at indexes (0, 1), (2, 3)...are equal until the uniquely existed element is visited.


low = 0;
high = 12;
middle = (0 + 12) / 2 = 6

Execute below steps until low < high.

Step 1: If middle is even, then check arr[middle], arr[middle+1] for equality
If middle is odd, the compare arr[mid-1] and arr[mid] for equality

Step 2: If the elements are matched in step1, elements till middle are perfect and the unique element exist at right side, we need to traverse right side.
         Low = middle + 1;
Repeat step 1.

Step 3: If the elements are not matched in step1, we need to traverse left side.


Find the below working application.
package com.sample.arrays;

import java.util.Arrays;

public class ArrayUtil {

    /**
   * In <code>arr</code>, all the numbers, except one number repeated twice, and
   * one number repeated only once. This method return the elements that is not
   * repeated.
   * 
   * @param arr
   * @return
   */
    public static int getUniqueElement(int arr[]) {
        if (arr == null || arr.length == 0) {
            throw new IllegalArgumentException("arrar couldn't be null");
        }

        Arrays.sort(arr);
        int low = 0;
        int high = arr.length - 1;
        int middle = (low + high) / 2;

        while (low < high) {
            if (middle % 2 == 0) {
                if (arr[middle] == arr[middle + 1]) {
                    low = middle + 2;
                } else {
                    high = middle;
                }
            } else {
                if (arr[middle] == arr[middle - 1]) {
                    low = middle + 1;
                } else {
                    high = middle;
                }
            }
            middle = (low + high) / 2;
        }

        return arr[low];
    }
}

Time complexity : O(n log n)
Time to sort the elements = O(n log n)
Time to do binary search = O(log n)
Total time  = O(n log n) + O (log n) = O(n log n).

Approach 4: Use set to find out the element.

Traverse the array one by one, insert the element into the set, if it is not existed. delete the element form set, if it is existed in the set.


Once you traverse complete array, there is only one element exist in the set, that is the uniquely existed one.
package com.sample.arrays;

import java.util.HashSet;
import java.util.Set;

public class ArrayUtil {

    /**
   * In <code>arr</code>, all the numbers, except one number repeated twice, and
   * one number repeated only once. This method return the elements that is not
   * repeated.
   * 
   * @param arr
   * @return
   */
    public static int getUniqueElement(int arr[]) {
        if (arr == null || arr.length == 0) {
            throw new IllegalArgumentException("arrar couldn't be null");
        }

        Set<Integer> set = new HashSet<> ();
        
        for(int ele : arr) {
            if(set.contains(ele)) {
                set.remove(ele);
            }else {
                set.add(ele);
            }
        }
        
        for(int ele : set) {
            return ele;
        }
        
        throw new IllegalArgumentException("Array is not satisfying input criteria");
        
        
    }
}

Time complexity: O(n)
As compared to previous approaches, it consumes more memory.

Approach 5: Using Ex-Or operation.

If you perform ex-or operation on same elements, the result is 0.

a ^ a = 0

If you perform ex-or operation with 0, then the result is always that element.

a ^ 0 = 0 ^ a = always


Since except one element, all the other elements repeated twice, when you perform Ex-Or of all the elements in array, the final outcome is the uniquely existed element.
package com.sample.arrays;

public class ArrayUtil {

    /**
   * In <code>arr</code>, all the numbers, except one number repeated twice, and
   * one number repeated only once. This method return the elements that is not
   * repeated.
   * 
   * @param arr
   * @return
   */
    public static int getUniqueElement(int arr[]) {
        if (arr == null || arr.length == 0) {
            throw new IllegalArgumentException("arrar couldn't be null");
        }

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

Time Complexity: O(n)


Find the unit test cases for above all approaches.
package com.sample.arrays;

import static org.junit.Assert.assertEquals;

import org.junit.Test;

/**
 * 
 *Test case method names follow below format.
 *{methodName}_{input}_{expectedOutput}
 *
 */
public class ArrayUtilTest {

    @Test(expected=IllegalArgumentException.class)
    public void getUniqueElement_nullArray_IllegalArgumentException() {
        ArrayUtil.getUniqueElement(null);
    }
    
    @Test(expected=IllegalArgumentException.class)
    public void getUniqueElement_emptyArray_IllegalArgumentException() {
        int arr[] = new int[0];
        ArrayUtil.getUniqueElement(arr);
    }
    
    @Test
    public void getUniqueElement_input1_returnCorrectResult() {
        int arr[] = {1, 2, 3, 4, 4, 3, 5, 2, 1};
        assertEquals(5, ArrayUtil.getUniqueElement(arr));
    }
    
    @Test
    public void getUniqueElement_input2_returnCorrectResult() {
        int arr[] = {100, 6, 100};
        assertEquals(6, ArrayUtil.getUniqueElement(arr));
    }
}


You may like


No comments:

Post a Comment