3

given a set of N numbers, i am supposed to find the odd one out. now N is an odd number, and the way to determine the 'odd one out' is by pairing the given numbers together, and eventually you'll be left with one number, which is the 'odd one out' .

The numbers are paired according to the distance between them. So first, two numbers with the least distance between them are picked from the given set of numbers and paired together. This leaves us with N-2 numbers in the set. The process is repeated until there is only 1 number left.

example: {1,4,3}

the distance between 1 and 3 is 2 and the distance between 3 and 4 is just 1. So 3 and 4 are paired which leaves us with 1 unpaired making it the odd man.

So far all i could think of is to sort the given list, and find the difference between each of the numbers and eliminate pairs, starting with the pair with the least distance between them. This would eventually land me with the 'odd one out' but the problem has to be solved with an algorithm that has a complexity less than O(N^2). Some help in the right direction would be greatly appreciated. Thank you

one more example: {1,3,4,6,10}

pair with least difference 3,4 eliminate pair -> {1,6,10} pair with least difference 6,10 eliminate pair -> {1} is the odd one out

another example {2,4,1,10,8,9,6}

pair with least difference (1,2) (8,9) and (9,10). eliminate (1,2) and (8,9) or (10,9) doesn't matter (for similar distances result can go either way; unpredictable) lets pick (8,9) -> {4,10,6}

next eliminate (4,6) --> {10} is the odd one out note: could have picked (9,10) instead of (8,9) as well.

i hope this clears up things

Priyath Gregory
  • 927
  • 1
  • 11
  • 37
  • Why your example didn't take 1 and 3 into account? Only adjacent element are candidates? – amit Feb 15 '15 at 12:47
  • @BoristheSpider Not sure you read the question carefully enough. Pairs with least distance are removed until a single number is left. If the number in the middle is distance one from adjacent then it'll be immediately eliminated. – sprinter Feb 15 '15 at 12:50
  • @sprinter you're right. I read _greatest_ rather than _least_. – Boris the Spider Feb 15 '15 at 12:51
  • What should be the answer if the input is first n natural numbers? like say 1,2,3,4,5,6,7,8,9 – Anil Feb 15 '15 at 13:07
  • If my the set is 1,2,3,4,6. If I pair 2 and 3,then I have to pair 4 and 6, the odd man is 1, if I pair 1 and 2, 3 and 4, the odd man is 6. which is the right answer? – Anil Feb 15 '15 at 13:26
  • 1
    Is your second example correct? How do you end up with `{4, 6, 10}` remaining after eliminating `{3, 4}`? Shouldn't it be `{1, 6, 10}` and `1` is the odd one out? – IVlad Feb 15 '15 at 13:27
  • @Anil in that case, there is no one correct answer, you can go either way. – Priyath Gregory Feb 15 '15 at 13:47
  • @IVlad yes you are right, there was a mistake. fixed now – Priyath Gregory Feb 15 '15 at 13:48

1 Answers1

2

One possible O(nlogn) solution is as follows:

  1. Sort the array (in O(nlogn) time).
  2. Compute the differences between adjacent elements in the sorted array.
  3. Store the difference values (along with the respective pairs) in a min-heap.
  4. Pop out the top pair from the min-heap. For every popped out pair, you will have to add another pair to the heap. This will be corresponding to the adjacent elements from the popped out pair. For example if the array was {...., 3, 5, 6, 9, ....} and the popped out pair was {5,6}, then add another pair in the heap {3,9} with a difference value of 6.
  5. Also, keep track of the elements already popped out (probably in a hash table) and simply reject any popped pair for which any of the elements is already popped out.
  6. Once the heap is empty, the element that was not included in any valid popped out pair shall be the odd one out.
Abhishek Bansal
  • 12,589
  • 4
  • 31
  • 46
  • 1
    @user269952 since 120 is the cornermost element there is no element to its immediate right, hence no pair shall be added in this case. – Abhishek Bansal Feb 15 '15 at 15:24
  • i think i got it. implementing, will let you know how things go. thank you – Priyath Gregory Feb 15 '15 at 15:41
  • to anyone wondering, ^^ is a reply to this comment which i removed "Tried out you're algorithm for the numbers {1,100,110,111,120}. As i understood it the minimum difference pair (1,110,111) would be at the top of the heap. I pop it out, and at the same time add (10,100,120) to the heap because 100 and 120 are the adjacent numbers to the popped out pair. now does this addition go on top of the heap? making my next pop the same tuple i've just added in? Then the next pop would be, (10,100,120) and now there is a problem. what should be the next adjacent pair i should add to the heap?" – Priyath Gregory Feb 15 '15 at 15:46
  • wouldn't step 4 make the complexity O(N^2) , popping from the heap and at each iteration scanning through an array to find the adjacent pairs, and finally doing a sorted insert on the heap? – Priyath Gregory Feb 15 '15 at 19:34
  • @user269952 No. Along with the pair values, just store their indices as well. Then accessing thier neighbours (if there exist) is O (1) operation. – Abhishek Bansal Feb 16 '15 at 03:00
  • what about inserting the adjacent pair back into the heap? i'll need to do a sorted insert right.. – Priyath Gregory Feb 16 '15 at 08:41
  • 1
    @user269952 As I mentioned, after popping a pair, you will need to insert the adjacent pair back in the heap. The heap structure shall ensure that the new pair falls in its correct place. – Abhishek Bansal Feb 16 '15 at 08:57
  • ok one final question, what sort of data structure should i use to store the difference,pair,and indices together? – Priyath Gregory Feb 16 '15 at 09:12
  • That depends on the language. If you are using C or C++, you can use a struct or class (in C++). Every language has a provision for a composite data type. The difference value field shall be used to compare betweens elements of the heap. – Abhishek Bansal Feb 16 '15 at 09:18
  • i have to implement this in java, so what would you recommend? – Priyath Gregory Feb 16 '15 at 09:20
  • dude! ur a life saver! everything worked beautifully :) THANK YOU – Priyath Gregory Feb 16 '15 at 12:39