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