re: Daily Challenge #108 - Find the Counterfeit Coin VIEW POST

FULL DISCUSSION
 

While one might be tempted at first to weigh all coins in pairs, requiring up to n/2 weightings, we can also weigh multiple coins at once. If we split the number of coins in two equal piles of coins, the pile with the counterfeit coin will weigh less. We can then split that pile and weigh those piles, until we are down to two coins.
One might wonder, as I did at first, "what happens when you have an odd number of coins?" In this case, you can take one coin out, and you have an even number of coins. Either the counterfeit coin is in one of the two piles you are weighing and one pile is therefore lighter, or the counterfeit coin is the one you took out and the two piles are equally weighted.
While you could simulate this very easily with the following function:

function numWeighings($numCoins) {
    if ($numCoins <= 1) {
        return 0;
    }

    return numWeighings(floor($numCoins / 2)) + 1;
}

this is, in fact, the logarithm of the number of coins in base two, which can be coded as such:

function numWeighings($numCoins) {
    return floor(log($numCoins, 2));
}

(and yes I had to double check if it was, indeed, the logarithm, by testing both functions up to 10000000)

 

It can be actually done in much fewer measurements by dividing the pile in thirds. This way even in the worst scenario you reduce the number of coins by the biggest possible amount in every step.

Imagine 100 coins. Divide it into piles of 33, 33, 34 and measure the equal ones. This way you end up with at most 34 for the next step as opposed to 50 if you were to divide the pile only in half.

 

The original problem that I heard was with 9 coins given 1 counterfeit, to find it with 2 measurements.

 

Good one! This changes it to the following code:

function numWeightings($numCoins) {
    if ($numCoins <= 1) {
        return 0;
    }


    return numWeightings(ceil($numCoins / 3)) + 1;
}

which is equal to

function numWeightings($numCoins) {
    return ceil(log($numCoins, 3));
}
code of conduct - report abuse