Enter your Email Address:

Delivered by FeedBurner

To get posts delivered to your Email

15 August 2010

Puzzle - Find the Unique Number

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:

Pravi said...

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.

Lakshmi Narayanan N said...

@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}

Pravi said...

Thanks Laxmi. Will it not work for this scenario?...Praveen Chiguru

Lakshmi Narayanan N said...

@bosu
You only posted this. try it out and let me know the answer.. :-)

welcome to my blog..

Yuvaraj N said...

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;
}

Lakshmi Narayanan N said...

@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;
}

Sandy said...

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);
}
}

Sandy said...

@Lakshmi,

Fantastic solution.. so simple and yet so effective.. avoids searching/sorting !!!

Kudos !!

Yuvaraj N said...

@Lakshmi,

Nice Solution. WQas looking for other variation's in your post like before. :)

Lakshmi Narayanan N said...

@Sandy
good try.

@Yuvi
No variation for this. will post another puzzle tonight. (may be in data structure)

Lakshmi Narayanan N said...

@All

Posted another puzzle on Binary Tree. Please check it out.

Have a Great Day.

ArunMozhi said...

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.,

Lakshmi Narayanan N said...

@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.