Find 1s in almost all 0 array using comparisons only

Question

So, we are given a 100 long array, with 97 0s and 3 1s of which we do not know the locations. We must find them using only a compare function, which I managed to write (in Python):

def compare(i, j):
    comparisons.append((i, j))
    if data[i] == data[j]:
        return 0 
    else:
        return 1 if data[i] > data[j] else -1

Using this function, we must find all three 1s with using at most 73 comparisons. We must output the compared pairs as a tuple as well as the coordinates of the three 1s.

Now, I tried writing a code with the following logic:

And I thought that maybe because two 1s will use 2 instead of 3 comparisons, it might come down do 73. This was not only long to code (I am studying mathematics, not CS), but I wrote to my prof, and he said this wouldn't work, and that I should try dynamic programming. I'm a bit lost, as I've never solved a coding program that is this limiting, so I have an other idea, which is to do a first parse of the array, going in pairs, so comparing (data[0], data1),(data[2], data[3]),.... This way, no matter how the 1s are placed, I ought to find at least one of them. I would also store all of the results of these comparisons, and then cross-check them with a set of new comparisons, namely (data1,data[2]),(data[5],data[6]),...

Any help is appreciated, specific code would be most useful, so I can understand how such a method would work.

Edit: I almost have it now thanks to @orlp, but I don't see why I still get 75 comparisons:

comparisons = []

def compare(i, j):
 comparisons.append((i, j))
 if data[i] == data[j]:
   return 0 
 else:
   return 1 if data[i] > data[j] else -1

def find_ones(data):
 found_ones = []

 for i in range(0, len(data), 2):
   if compare(i, i + 1) != 0:
     found_ones.append(i if data[i] == 1 else i + 1)
     if len(found_ones) == 3:
       return comparisons, found_ones[0], found_ones[1], found_ones[2]

 remaining_pairs = [i for i in range(0, len(data), 2) if i not in found_ones]
 for i in range(0, len(remaining_pairs) - 1, 2):
   if compare(remaining_pairs[i], remaining_pairs[i + 1]) != 0: 
     found_ones.extend([remaining_pairs[i], remaining_pairs[i + 1]])
     break

 if len(found_ones) == 1:
   found_ones.extend(remaining_pairs[-2:])

 return comparisons, found_ones[0], found_ones[1], found_ones[2]


def get_input_data():
 position_1 = int(input("Enter position of first '1' (0-99): "))
 position_2 = int(input("Enter position of second '1' (0-99): "))
 position_3 = int(input("Enter position of third '1' (0-99): "))

 data = [0] * 100
 data[position_1] = data[position_2] = data[position_3] = 1
 return data


data = get_input_data()
comparisons, a, b, c = find_ones(data.copy()) 

print("Comparisons:")
for pair in comparisons:
 print(pair)

print("\nPositions of '1's:")
print(a, b, c)

print("\nNumber of comparisons:", len(comparisons))

I included the optimizations at the end, didn't I? Don't do the last comparison, if only one 1 has been found the first time around, and the second time don't do the last comparison, because by then we know them to be 1s.

Edit 2: I fixed, some of the issues in the first half, but I just do not see why it isn't down to 73 steps. Also now, it is returning false values. What am I doing wrong?

comparisons = []
    
def compare(i, j):
    comparisons.append((i, j))
    if data[i] == data[j]:
        return 0 
    else:
        return 1 if data[i] > data[j] else -1

def find_ones(data):
    found_ones = []

    # Step 1: Initial pairing and comparisons
    for i in range(0, len(data)-2, 2):
        if compare(i, i + 1) != 0:  # One of them is a '1'
            found_ones.append(i if data[i] == 1 else i + 1)
            if len(found_ones) == 3:  # Found all three '1's
                return comparisons, found_ones[0], found_ones[1], found_ones[2]

            
            
      # Check if we need to compare the final pair
    if len(found_ones) == 2:
        result = compare(len(data) - 2, len(data) - 1)
        if result == 1:   # '1' is at index len(data) - 2
          found_ones.append(len(data) - 2)
        elif result == -1:  # '1' is at index len(data) - 1
          found_ones.append(len(data) - 1)
        
    if len(found_ones) == 3:  # Found all three '1's
                return comparisons, found_ones[0], found_ones[1], found_ones[2]

            
    # Step 2: Find the pair with the remaining two '1's
    remaining_pairs = [i for i in range(0, len(data), 2) if i not in found_ones]
    for i in range(0, len(remaining_pairs) - 1, 2):
        if compare(remaining_pairs[i], remaining_pairs[i + 1]) != 0:  # Found the (1, 1) pair
            found_ones.extend([remaining_pairs[i], remaining_pairs[i + 1]])
            break

    # Step 3: If necessary, deduce the last pair
    if len(found_ones) == 1:
        found_ones.extend(remaining_pairs[-2:])  # The remaining pair must be (1, 1)

    return comparisons, found_ones[0], found_ones[1], found_ones[2]


# Example usage
def get_input_data():
    # Replace this with your preferred input method (e.g., user input)
    position_1 = int(input("Enter position of first '1' (0-99): "))
    position_2 = int(input("Enter position of second '1' (0-99): "))
    position_3 = int(input("Enter position of third '1' (0-99): "))

    data = [0] * 100
    data[position_1] = data[position_2] = data[position_3] = 1
    return data


data = get_input_data()
comparisons, a, b, c = find_ones(data.copy())  # Use copy to avoid modifying original 

print("Comparisons:")
for pair in comparisons:
    print(pair)

print("\nPositions of '1's:")
print(a, b, c)

print("\nNumber of comparisons:", len(comparisons))

Edit 3:

comparisons = []
   
def compare(i, j):
  comparisons.append((i, j))
  if data[i] == data[j]:
    return 0 
  else:
    return 1 if data[i] > data[j] else -1

def find_ones(data):
  found_ones = []
  excluded_indices = set()  # Track indices already found

  # Step 1: Initial pairing and comparisons
  for i in range(0, len(data) - 2, 2): 
    result = compare(i, i + 1)
    if result == 1:  
     found_ones.append(i)
     excluded_indices.update({i, i + 1})  # Update excluded indices
    elif result == -1: 
     found_ones.append(i + 1)
     excluded_indices.update({i, i - 1})  # Update excluded indices

    if len(found_ones) == 3: 
        return comparisons, found_ones[0], found_ones[1], found_ones[2]
   
   # Check if we need to compare the final pair
  if len(found_ones) == 2 and (len(data) - 2) not in excluded_indices and (len(data) - 1) not in excluded_indices: 
    result = compare(len(data) - 2, len(data) - 1)
    if result == 1:  
     found_ones.append(len(data) - 2)
     excluded_indices.update({len(data) - 2, len(data) - 1})  # Update excluded indices
    elif result == -1: 
     found_ones.append(len(data) - 1)
     excluded_indices.update({len(data) - 2, len(data) - 1})  # Update excluded indices

  if len(found_ones) == 3:
        return comparisons, found_ones[0], found_ones[1], found_ones[2]
       
  # Step 2: Find the pair with the remaining two '1's
  remaining_pairs = [i for i in range(0, len(data), 2) if i not in excluded_indices] 
  for i in range(0, len(remaining_pairs) - 1, 2):
    if compare(remaining_pairs[i], remaining_pairs[i + 1]) != 0:
      found_ones.extend([remaining_pairs[i], remaining_pairs[i + 1]])
      break

  # Step 3: If necessary, deduce the last pair
  if len(found_ones) == 1:
    found_ones.extend(remaining_pairs[-2:])

  return comparisons, found_ones[0], found_ones[1], found_ones[2]

# Example usage
def get_input_data():
    position_1 = int(input("Enter position of first '1' (0-99): "))
    position_2 = int(input("Enter position of second '1' (0-99): "))
    position_3 = int(input("Enter position of third '1' (0-99): "))

    data = [0] * 100
    data[position_1] = data[position_2] = data[position_3] = 1
    return data


data = get_input_data()
comparisons, a, b, c = find_ones(data) 
print("Comparisons:")
for pair in comparisons:
    print(pair)

print("\nPositions of '1's:")
print(a, b, c)

print("\nNumber of comparisons:", len(comparisons))

Edit 4: Okay, I believe I fixed the wrong excluding of the indexes, I now see how in both cases it must be i and i + 1. I still don't see how the logic in step 3 is wrong, but I did try to fix it in step 2. If we are in step 2 we still have an even number of elements, all of which hae previously been compared in pairs. Let's say we are here: (0,0)(1,1), where the parentheses mark the compared pairs from the first parse. The i-th element is the first zero of a pair (or the first 1 of a pair), so we compare it with the element that is 2 away from it, meaning the first element of the other pair. In this case we get remaining_pairs(i)<remaining_pairs(i+2), so we add i+2 and i+3 as being 1s. If it was the other way around, then we add i and i+1. It is still slightly off though, what is wrong?

comparisons = []

def compare(i, j):
  comparisons.append((i, j))
  if data[i] == data[j]:
    return 0 
  else:
    return 1 if data[i] > data[j] else -1

def find_ones(data):
  found_ones = []
  excluded_indices = set()  # Track indices already found

  # Step 1: Initial pairing and comparisons
  for i in range(0, len(data) - 2, 2): 
    result = compare(i, i + 1)
    if result == 1:  
     found_ones.append(i)
     excluded_indices.update({i, i + 1})  # Update excluded indices
    elif result == -1: 
     found_ones.append(i + 1)
     excluded_indices.update({i, i + 1})  # Update excluded indices

    if len(found_ones) == 3: 
        return comparisons, found_ones[0], found_ones[1], found_ones[2]

   # Check if we need to compare the final pair
  if len(found_ones) == 2 and (len(data) - 2) not in excluded_indices and (len(data) - 1) not in excluded_indices: 
    result = compare(len(data) - 2, len(data) - 1)
    if result == 1:  
     found_ones.append(len(data) - 2)
     excluded_indices.update({len(data) - 2, len(data) - 1})  # Update excluded indices
    elif result == -1: 
     found_ones.append(len(data) - 1)
     excluded_indices.update({len(data) - 2, len(data) - 1})  # Update excluded indices

  if len(found_ones) == 3:
        return comparisons, found_ones[0], found_ones[1], found_ones[2]

  # Step 2: Find the pair with the remaining two '1's
  remaining_pairs = [i for i in range(0, len(data), 2) if i not in excluded_indices] 
  for i in range(0, len(remaining_pairs) - 1, 2):
    result=compare(remaining_pairs[i], remaining_pairs[i + 2])
    if result == 1:
      found_ones.extend([remaining_pairs[i], remaining_pairs[i + 1]])
      break
    elif result == -1:
      found_ones.extend([remaining_pairs[i+2], remaining_pairs[i + 3]])
      break
    
  # Step 3: If necessary, deduce the last pair
  if len(found_ones) == 1:
    found_ones.extend(remaining_pairs[-2:])

  return comparisons, found_ones[0], found_ones[1], found_ones[2]

def get_input_data():
    position_1 = int(input("Enter position of first '1' (0-99): "))
    position_2 = int(input("Enter position of second '1' (0-99): "))
    position_3 = int(input("Enter position of third '1' (0-99): "))

    data = [0] * 100
    data[position_1] = data[position_2] = data[position_3] = 1
    return data


data = get_input_data()
comparisons, a, b, c = find_ones(data) 
print("Comparisons:")
for pair in comparisons:
    print(pair)

print("\nPositions of '1's:")
print(a, b, c)

print("\nNumber of comparisons:", len(comparisons))

Edit 5: Do I have it?

comparisons = []

def compare(i, j):
  comparisons.append((i, j))
  if data[i] == data[j]:
    return 0 
  else:
    return 1 if data[i] > data[j] else -1

def find_ones(data):
  found_ones = []
  excluded_indices = set()  # Track indices already found

  # Step 1: Initial pairing and comparisons
  for i in range(0, len(data) - 2, 2): 
    result = compare(i, i + 1)
    if result == 1:  
     found_ones.append(i)
     excluded_indices.update({i, i + 1})  # Update excluded indices
    elif result == -1: 
     found_ones.append(i + 1)
     excluded_indices.update({i, i + 1})  # Update excluded indices

    if len(found_ones) == 3: 
        return comparisons, found_ones[0], found_ones[1], found_ones[2]

   # Check if we need to compare the final pair
  if len(found_ones) == 2 and (len(data) - 2) not in excluded_indices and (len(data) - 1) not in excluded_indices: 
    result = compare(len(data) - 2, len(data) - 1)
    if result == 1:  
     found_ones.append(len(data) - 2)
     excluded_indices.update({len(data) - 2, len(data) - 1})  # Update excluded indices
    elif result == -1: 
     found_ones.append(len(data) - 1)
     excluded_indices.update({len(data) - 2, len(data) - 1})  # Update excluded indices

  if len(found_ones) == 3:
        return comparisons, found_ones[0], found_ones[1], found_ones[2]

  # Step 2: Find the pair with the remaining two '1's
  remaining_pairs = [i for i in range(0, len(data)) if i not in excluded_indices] 
  for i in range(0, len(remaining_pairs) - 2, 4):
    result=compare(remaining_pairs[i], remaining_pairs[i + 2])
    if result == 1:
      found_ones.extend([remaining_pairs[i], remaining_pairs[i + 1]])
      break
    elif result == -1:
      found_ones.extend([remaining_pairs[i+2], remaining_pairs[i + 3]])
      break
    
  # Step 3: If necessary, deduce the last pair
  if len(found_ones) == 1:
    found_ones.extend(remaining_pairs[-2:])

  return comparisons, found_ones[0], found_ones[1], found_ones[2]

def get_input_data():
    position_1 = int(input("Enter position of first '1' (0-99): "))
    position_2 = int(input("Enter position of second '1' (0-99): "))
    position_3 = int(input("Enter position of third '1' (0-99): "))

    data = [0] * 100
    data[position_1] = data[position_2] = data[position_3] = 1
    return data


data = get_input_data()
comparisons, a, b, c = find_ones(data) 
print("Comparisons:")
for pair in comparisons:
    print(pair)

print("\nPositions of '1's:")
print(a, b, c)

print("\nNumber of comparisons:", len(comparisons))
```

Answer 1

Start by splitting the 100 elements in 50 pairs of two, and use a comparison on each pair. If a comparison returns -1 or 1, then you've found one of the elements which is 1 (and the other one must be a 0).

Now there are two cases after these 50 comparisons: either we've found all three 1's, or we've found one 1, because the remaining two were part of the same pair. In the latter case we must find the pair which contains the last two 1's.

In this case there will be 49 pairs left (we can exclude the (0, 1) pair we identified earlier) one of which is the (1, 1) pair. We can find it by pairing the pairs, and doing one comparison each (for a total of 24 comparisons, leaving one pair out). This will identify which pair is the one with (1, 1), or if not, we know it must be the last pair.

This gives a total of 74 comparions. In fact, we could have saved one more comparison in the first step by stopping after 49 comparisons. If we have found two 1's in those first 49 comparisons we do one more to find the last 1 and we are done, and if we've found only one 1 it's useless to perform the comparison on the last pair, as it could only be (0, 0) or (1, 1), giving us no information.

Answer 2

Your current code has the following issues:

for i in range(0, len(data), 2):

This is where you need to put the optimization to (conditionally) avoid comparing the final pair. You have two options for how to do that optimization:

• Subtract 2 from the endpoint of the range, and then check after the loop for whether comparing the final pair is necessary.
• Or check inside the loop whether the current pair is the final pair and whether comparing the final pair is necessary. If it's the final pair and comparing it is not needed, then skip the compare call.

Choose one or the other of those solutions, not both.

found_ones.append(i if data[i] == 1 else i + 1)

Checking the value of data[i] in this line breaks the problem requirement of only checking data values in the compare function. You need to instead check whether the returned result from compare is 1 or -1 to determine which element in the pair is the 1. In doing this, you will also need to avoid making duplicate compare calls. One way to avoid the duplicate call is to use a match statement. Another is to save the result value to a variable so you can check that variable for the value multiple times without re-invoking the function call.

remaining_pairs = [i for i in range(0, len(data), 2) if i not in found_ones]

This does not reliably filter out the pair that you found a 1 in. It filters the indexes of the first element in each pair, and fails to filter out the found pair if the found 1 is the second element in its pair.

if compare(remaining_pairs[i], remaining_pairs[i + 1]) != 0:

This neglects to check which of the two pairs is a pair of 1s and which is a pair of 0s. Do this by checking whether the return value is 1 or -1, and again make sure to avoid duplicate compare calls as I noted earlier.

found_ones.extend([remaining_pairs[i], remaining_pairs[i + 1]])

This adds the first element of each of the pairs. It should instead be adding both elements of one of the pairs. Make sure to use the result of the compare call to determine which pair to add.

found_ones.extend(remaining_pairs[-2:])

Same problem as the previous one. This adds the first element of each of the last two pairs. It should instead be adding both elements of the last pair.

Edit responding to your comment and "Edit 2":

I tried to implement some of your advice, and I do not see how I am wrong. I corrected the inappropriate use of something other than my compare function, but I can't get the logic right with the optimizations.

You fixed the inappropriate check of data[i] in your new post-loop check of the final pair, but it's still there in the first loop itself.

Now, going through your code responses to the issues in order:

1. Conditional compare of the final pair for the first loop: You solved this correctly.
2. Checking the return value of compare instead of directly checking data[i]: You only partially finished this. You got it right for the final pair, but you need to also apply the same fix inside the first loop.
3. Fixing the buggy filtering of remaining_pairs: You missed this completely, and it will sometimes cause incorrect results until you fix it. As an example to show the issue, consider the data set [0, 0, 0, 1, 0, 0, ..., 1, 1]. After the first loop, found_ones will be [3]. The filter you use to fill remaining_pairs will check if 2 is in found_ones, find it is not, and will include 2 in the resulting value of remaining_pairs. This is a bug because the 2 index is the other element of the pair that the 1 was found in and should therefore be excluded from remaining_pairs.
4. Checking the return value of compare to find which pair has the remaining two 1s: You missed this completely. Some inputs will get wrong results until this is fixed.
5. Fixing which index values to add after finding the last two 1s in the second loop: You missed this completely. Some inputs will get wrong results until this is fixed. For example, consider the data set [0, 0, 1, 1, 0, 0, ..., 0, 1]. The current code will report that it found 1s at positions 0 and 2 (and 99 but that's irrelevant to this issue), but the correct result is that those first two 1s are at positions 2 and 3.
6. Fixing which index values to add after finding that the last two 1s are the last pair: You missed this completely. Inputs where the last two data values are 1s will get wrong results until this is fixed.

Responding to "Edit 3":

1. excluded_indices is a good addition, but one of the update calls on it is wrong. The correct indices to exclude when you find a 1 in the first loop are always {i, i + 1}, because that is the pair that you compared regardless of which part of the pair is the 1.
2. This one technically isn't wrong, as in it won't cause your code to produce incorrect results, but checking excluded_indices in the condition for comparing the final pair is pointless. The indices of the final pair cannot possibly be in excluded_indices at that point in the code, because the final pair hasn't been checked yet.
3. You still haven't fixed issues 4, 5, and 6 from my previous edit. Those are for the sections of code that you labeled as step 2 and step 3.