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

re: 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 sp...

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