My issue
Brute Force
The most naive implementation would be to check each coin one by one.
That is, first take any two coins. Let’s say we take coins indexed 1 and 2.
Now we will measure these coins against each other; if the weight scale shows deflection, then the lighter coin will be the fake one. Otherwise, both of these will be real. We will then take any one of these two coins and measure them against all the other coins one-by-one; eventually, we will find the fake coin.
Task
This algorithm is implemented in the IDE but is incomplete, complete it to solve the problem.
My code
import random
def measure(left, right):
sum_left = sum(A[i - 1] for i in left)
sum_right = sum(A[i - 1] for i in right)
if sum_left > sum_right:
return '>'
elif sum_left < sum_right:
return '<'
return '='
def solution(n):
a = [1]
b = [2]
c = measure(a, b)
if c == '=':
for i in range(3, n + 1):
if measure([1], [i]) == '>':
return i
return -1 # If no lighter coin is found, which shouldn't happen if there's exactly one fake coin
elif c == '<':
return 1
else:
return 2
# Testing the function
# Example configuration
# Let's create an example list where the weights are mostly equal but one is lighter
n = 10
A = [1] * n
fake_coin_index = random.randint(0, n-1)
A[fake_coin_index] = 0 # The fake coin is lighter
print(f"Fake coin is at position: {fake_coin_index + 1}")
print("Detected fake coin position:", solution(n))
Learning course: Analysis and Design of Algorithms
Problem Link: Brute Force in Analysis and Design of Algorithms