There are two arrays - a and b. One of the arrays contains one element more than the other. The extra element is unique and all other elements are same but in different order. Find the element that is unique.
For example
a -> {10,2,3,4,6,5,8,7,9,1}
b -> a -> {1,2,3,4,5,6,7,8,9}
Unique element is {10}
Answer
public static int getUniqueKey(int[] bigger, int[] smaller) {
if(bigger == null || smaller == null || Math.abs(bigger.length - smaller.length) != 1) {
throw new ArithmeticException("arguments passed is null.");
}
// Till now, bigger is not necessarily bigger. let us make it bigger
if(bigger.length < smaller.length) {
int[] temp = smaller;
smaller = bigger;
bigger = temp;
}
int biggerValue = 0;
int smallerValue = 0;
for(int i = 0; i < smaller.length; ++i) {
biggerValue += bigger[i];
smallerValue += smaller[i];
}
biggerValue += bigger[bigger.length - 1];
return biggerValue - smallerValue;
}
Let us discuss one more puzzle in upcoming days in this week.
13 comments:
for (i=0, j=0; i<n, j<m; i++, j++)
{
if (a[i]!=a[j])
j++;
else
print {"unique no: %d", a[i]};
j=i++;
}
I am out of touch from programing for so many years, But I just tried :-). Forgive me for any syntax or semantics errors.
@Pravi
Very sorry. The numbers in the both arrays are not in same order. For example
a ->{10,2,3,4,6,5,8,7,9,1}
b -> {1,2,3,4,5,6,7,8,9}
Unique element is {10}
Thanks Laxmi. Will it not work for this scenario?...Praveen Chiguru
@bosu
You only posted this. try it out and let me know the answer.. :-)
welcome to my blog..
static int FindUnique(int[] a, int[] b)
{
int uniqueNumber = -1;
// Shifting bigger array to a
if (a.Length < b.Length)
{
int[] temp = a;
a = b;
b = temp;
}
for (int i = 0; i < a.Length; i++)
{
int j = i;
for (; j < b.Length; j++)
{
if (b[j] == a[i])
{
// Found corresponding number in b array
// Changing b array to bubble found numbers to top
b[j] = b[i];
b[i] = a[i];
break;
}
}
if (j == b.Length)
{
// Found unique number
uniqueNumber = a[i];
break;
}
}
return uniqueNumber;
}
@Yuvi
Good try.
Here is another version of answer.
public static int getUniqueKey(int[] bigger, int[] smaller) {
if(bigger == null || smaller == null || Math.abs(bigger.length - smaller.length) != 1) {
throw new ArithmeticException("arguments passed is null.");
}
// Till now, bigger is not necessarily bigger. let us make it bigger
if(bigger.length < smaller.length) {
int[] temp = smaller;
smaller = bigger;
bigger = temp;
}
int biggerValue = 0;
int smallerValue = 0;
for(int i = 0; i < smaller.length; ++i) {
biggerValue += bigger[i];
smallerValue += smaller[i];
}
biggerValue += bigger[bigger.length - 1];
return biggerValue - smallerValue;
}
package com.algo;
import java.util.Arrays;
public class FindUnique {
public static void main(String[] args) {
int[] a = {9,8,5,1,2,7,6,4,3};
int[] b = {10,7,9,1,3,2,5,8,6,4};
int[] temp;
FindUnique fu = new FindUnique();
fu.sortArrays(a,b);
if (b.length > a.length){
temp = a;
a = b;
b = temp;
}
for (int i:a){ // loop thru the larger array
int found = fu.binarySearch(b, i, 0, b.length-1);
if (found == -1){
System.out.println("Unique element: " + i);
break;
}
}
}
private void sortArrays(int []a, int []b){
Arrays.sort(a);
Arrays.sort(b);
}
// Param1 : The Array which is to be searched for
// Param2 : The value to be searched in the Array
// Begin Index : Initially passed as 0
// End Index : Initially passed as (Array.length - 1)
// Returns : The index position of element in array; -1 if not found
private int binarySearch(int[] array, int value, int left, int right) {
if (left > right)
return -1;
int middle = (left + right) / 2;
if (array[middle] == value)
return middle;
else if (array[middle] > value)
return binarySearch(array, value, left, middle - 1);
else
return binarySearch(array, value, middle + 1, right);
}
}
@Lakshmi,
Fantastic solution.. so simple and yet so effective.. avoids searching/sorting !!!
Kudos !!
@Lakshmi,
Nice Solution. WQas looking for other variation's in your post like before. :)
@Sandy
good try.
@Yuvi
No variation for this. will post another puzzle tonight. (may be in data structure)
@All
Posted another puzzle on Binary Tree. Please check it out.
Have a Great Day.
simple ,
We Can Add the values of the Array1 and Subtract With Another Array Total Values
We can Easily Get that Unique Number.
Thanks,
M.Sundar.,
@Sundar
Welcome to Unstuck.
Good, that is optimal way of doing.
BTW, did you check out other problems especially on finding common lowest parent of two given nodes in binary tree.
Hope to see your answers for that too.
Post a Comment