1

If I have two lists each with elements that can be one of two possible values and the two lists are identical except for one value, which method should I use to find the index of that value? I am going to code this in Python as background information

Method A: 

1. represent both lists as a binary literals  
2. use XOR on the two binary literals to give a value "v" that is a power of 2  
3. finally, use math.log(v, 2) to get the index

or Method B:

just iterate through both lists until a different element is found and 
get the index

or another way using Python?

Kevin Hwang
  • 83
  • 6

3 Answers3

2

Converting your lists to another representation would involve iterating through them -- might as well iterate to find the difference itself.

Michał Marczyk
  • 83,634
  • 13
  • 201
  • 212
  • 2
    This is assuming your lists are actually Python lists. If what you have is some textual representation of lists, say, then depending on what you intend to use them for it might make sense to represent them as numbers in memory, and in that case you should simply implement both approaches to finding the difference and measure which one is faster. – Michał Marczyk Jul 06 '13 at 06:14
1

I don't know about the "best" way, but you could use python to get the difference of two sets, and then return the index:

xs= [1, 2, 3, 4, 5]
ys = [1, 2, 3, 4, 6] # i.e. xs(5) and ys(6) are different


xs.index( list(set(xs) - set(ys))[0] )
ys.index( list(set(ys) - set(xs))[0] )
Nick Burns
  • 973
  • 6
  • 4
0

I think first method is better. You can modify it further.

xor the two list and store the result in a variable say k. Find a set bit in k. Now xor all the elements with this bit set to 1 . You will get one number. xor this number with k to get the other.

Find the two numbers in the lists to know which list each belongs to and indices of the numbers.

banarun
  • 2,305
  • 2
  • 23
  • 40