5

So this is the classic problem of finding a counterfeit coin among a set of coins using only a weighing balance. For completeness, here is one example of such a problem:

A well-known example has nine (or fewer) items, say coins (or balls), that are identical in weight save for one, which in this example is lighter than the others—a counterfeit (an oddball). The difference is only perceptible by weighing them on scale—but only the coins themselves can be weighed. Is it possible to isolate the counterfeit coin with only two weighings?

We are dealing with the case where only one of the coins is counterfeit and we know how it is so (i.e. we know it is heavier/lighter).

My question is, is there a general efficient algorithm to solve the generalized version of this problem for N coins with one counterfeit. I have been thinking about it and so far I have that if N is of the form 3^k, then you can find the counterfeit in ⌈log_3_(N)⌉ by splitting them into groups of three recursively. Is this true for all N, not jus those of the from 3^k and if so, can we do better?

gowrath
  • 3,136
  • 2
  • 17
  • 32
  • 3
    I'm voting to close this question as off-topic because belongs to programming.stackexchange.com or maths.stackexchange.com – DhruvPathak Sep 02 '16 at 07:21
  • @DhruvPathak Explain. I'm asking about the specific algorithm we could use; how is that not related to stackoverflow. See [here](http://stackoverflow.com/questions/14415881/how-to-pair-socks-from-a-pile-efficiently) and [here](http://stackoverflow.com/questions/22342854/what-is-the-optimal-algorithm-for-the-game-2048) and [here](http://stackoverflow.com/questions/137783/expand-a-random-range-from-1-5-to-1-7)... – gowrath Sep 02 '16 at 07:22
  • 2
    Why are you voting this as off-topic? This is about designing an algorithm, which would be equally valid on other sites, and perhaps a better fit on maths, but it's also on topic here. – Filip Haglund Sep 02 '16 at 07:28

5 Answers5

1

Unless you have any extra information about the input, ⌈log_3_(N)⌉ is the best you can reach. Three groups of equal number of coins, weigh two of them against each other, and you'll see which of the three groups has the lower weight. Recursively apply the same algorithm to the lightest group. Any left-over coins above k^3 is also kept for later rounds.

Filip Haglund
  • 13,919
  • 13
  • 64
  • 113
  • You say average case. What would be the best and worst cases then? – gowrath Sep 02 '16 at 07:52
  • 1
    For random input, `⌈log_3_(N)⌉` is the best, average and worst complexity. In the worst case, we get 2 coins left over, which we cannot check, until we reach the end. This adds at most one extra comparison at the end. The actual worst-case complexity would be `⌈log_3_(N)⌉ * 2 + 1`, for keeping the 2 extra coins around. – Filip Haglund Sep 02 '16 at 08:04
1

Let us say, you have N coins.

Make 3 groups of coins each containing floor(N/3) coins. If there are leftover coins (N%3), place them in the last(3rd) group. Note that the first 2 groups have same number of coins.

Weigh the 1st group with the 2nd group. If they are unequal, then we have to find the culprit(counterfeit coin) from one of these groups. So our solution space reduces to N/3 after the first weighing.

If they are equal, then the counterfeit coin is present in the 3rd group which has at max (N/3) + 2 coins.

Doing this recursively, lets us find the counterfeit in ceil(log_3_(N)) time.

User_Targaryen
  • 4,125
  • 4
  • 30
  • 51
0

Javascript code to solve counterfeit coin problem:

let coins = [3, 2, 3, 3, 3, 3, 3, 3, 3];
let weightUsageCount = 0;
var optimizeUsage = function (coins) {
  let n = coins.length;
  if (n < 1) {
    //If length is lower than 1, no coins are provided
    return -1;
  } else if (n == 1) {
    //If one coin left, it is the lighter coin
    printCoinInfo(coins[0]);
  } else {
    let set1 = coins.slice(0, parseInt(n / 2));
    let set2 = coins.slice(parseInt(n / 2), 2*(n/2));
    let set3 = coins.slice(2*parseInt(n/2), n);

    var coin = diffScale(set1, set2);
    if (coin == 0) {
      //Set 1 is lighter
      optimizeUsage(set1);
    } else if (coin == 1) {
      //Set 2 is lighter
      optimizeUsage(set2);
    } else {
      //Balanced
      optimizeUsage(set3);
    }
  }
};


var diffScale = function (coinSet1, coinSet2) {
  weightUsageCount++;
  let sum1 = coinSet1.reduce((a, b) => a + b, 0);
  let sum2 = coinSet2.reduce((a, b) => a + b, 0);
  
  if (sum1 < sum2) return 0;
  else if (sum2 < sum1) return 1;
  return -1;
};

var printCoinInfo = function(coin) {
  console.log("Array : "+JSON.stringify(coins)+ " | Total Coins : "+coins.length);
  console.log("Defect Coin Weight : "+coin);  
  console.log("Weight Scale Usage : "+ weightUsageCount+" Times");
}

optimizeUsage(coins);

See the JSFiddle Demo Here : https://jsfiddle.net/ShashiBadhuk/odtyms5g/

Shashi
  • 1,165
  • 5
  • 20
  • 39
0

Brute Force approach can be to go for a Linear Search but that will be of order N.

For optimized solution we can go for Binary Search kind of approach where in we keep dividing the search space by 2. This can bring it to order of log N base 2 complexity.

Manish Pushkar
  • 1
  • 1
-1

I've used this code, however sometimes it is off by 1((:

def how_many_measurements(n):
    import math
    if n<2:
        x = 0
    elif n >= 2 and n<=4:
        x = 1
    elif n>4 and n<12:
        x = 2
    else:
        x= math.ceil(math.log((2*n+1),3))
    return x
Aziz
  • 1