DEV Community

dev.to staff
dev.to staff

Posted on

6 1

Daily Challenge #108 - Find the Counterfeit Coin

Imagine you have 8 coins of equal weight, except for one. The odd one weighs less than the others because it is not made of pure gold. How many iterations are needed to find this counterfeit coin using a two plate scale?

Write a function that represents this logic puzzle and returns the minimum number of weightings it will take to measure n coins, without relying on luck at all. It can help to think recursively.

Good luck, have fun!


This challenge comes from GiacomoSorbi on CodeWars. Thank you to CodeWars, who has licensed redistribution of this challenge under the 2-Clause BSD License!

Want to propose a challenge idea for a future post? Email yo+challenge@dev.to with your suggestions!

Warp.dev image

The best coding agent. Backed by benchmarks.

Warp outperforms every other coding agent on the market, and gives you full control over which model you use. Get started now for free, or upgrade and unlock 2.5x AI credits on Warp's paid plans.

Download Warp

Top comments (6)

Collapse
 
dwilmer profile image
Daan Wilmer β€’ β€’ Edited

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)

Collapse
 
dwilmer profile image
Daan Wilmer β€’

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));
}
Collapse
 
matissg profile image
matissg β€’

Randomly selected coin and lighter/heavier its value with Ruby:

# frozen_string_literal: true

# Save file as coins.rb and run `ruby coins.rb`
class Coins
  def initialize(place, value)
    @coins = Array.new(7, 1).insert(place, value)
    @count = 0
  end

  def weight
    return puts @count if @coins.size == 1

    @count += 1
    step = @coins.size / 2
    first = @coins.first(step)
    last = @coins.last(step)
    @coins = first.sum > last.sum ? first : last
    weight
  end
end

Coins.new(rand(0..7), [0, 2].sample).weight
Enter fullscreen mode Exit fullscreen mode
Collapse
 
qm3ster profile image
Mihail Malo β€’

There's a modification where we don't know if the counterfeit is lighter or heavier, just that it will be different.
It is interesting because finding out if it is heavier or lighter is significant to picking the next pile to split.

Collapse
 
peledzohar profile image
Zohar Peled β€’

This is a very old question. I remember being asked this question about 25 years ago.

The answer is to divide to three groups, as equal as possible. You have 9 coins. You start by measuring 3 against 3. If one is lighter than the other, that's where the coin is, and you again split to 3 piles of one coin each and measure. If both are the same, the counterfeit coin is the one left out - meaning you only need two weightings to find the counterfeit.

Collapse
 
scrabill profile image
Shannon Crabill β€’

I've been thinking about this problem for a few days and each solution I can come up with is a tangled mess of comparative loops.

Dev Diairies image

User Feedback & The Pivot That Saved The Project

πŸ”₯ Check out Episode 3 of Dev Diairies, following a successful Hackathon project turned startup.

Watch full video πŸŽ₯

πŸ‘‹ Kindness is contagious

Dive into this thoughtful piece, beloved in the supportive DEV Community. Coders of every background are invited to share and elevate our collective know-how.

A sincere "thank you" can brighten someone's dayβ€”leave your appreciation below!

On DEV, sharing knowledge smooths our journey and tightens our community bonds. Enjoyed this? A quick thank you to the author is hugely appreciated.

Okay