Poor pigs

Link: https://leetcode.com/problems/poor-pigs/

Solution:

Topics: math, qubit

Intuition
Really weird problem, but the iterative approach kind of makes sense. I will improve this editorial upon future revisions.

The key insight seems to be the fact that in one round of testing, n pigs can test 2**n buckets. In two rounds of testing, n pigs can test 3**n buckets. Or more generally, (rounds+1)**n. Its a bit unclear to me why exactly this is the case, but I’m going to trust it for now and improve on this editorial later. This seems to be an encoding problem.

rounds = 1
states: [dead, alive] (2**num_pigs)

rounds = 2
states: [dead_in_rd1, dead_in_rd2, alive] (3**num_pigs)

rounds = 3
states: [dead_in_rd1, dead_in_rd2, dead_in_rd3, alive] (4**num_pigs)

We are given minutesToDie and minutesToTest, so we can compute how many complete rounds we have for testing.

rounds = minutesToTest // minutesToDie

Now its simply a matter of increasing the amount of pigs in the formula (rounds+1)**pigs until the result is greater or equal to the number of buckets provided to test.

Implementation

def poor_pigs(minutesToTest, minutesToDie, buckets):
	rounds = minutesToTest // minutesToDie
	pigs = 0
	while (rounds+1)**pigs < buckets:
		pigs += 1
	return pigs
 
#time: o(log(buckets))
#memory: o(1)

Instead of the while loop, we can also solve mathematically.

def poor_pigs(minutesToTest, minutesToDie, buckets):
	rounds = minutesToTest // minutesToDie
	return ceil(log2(buckets) / log2(rounds+1))
	
#time: o(1)
#memory: o(1)

Visual

visuals from this solution https://leetcode.com/problems/poor-pigs/solutions/935172/two-diagrams-to-help-understanding/

Review 1
Just remember that 1 pig can test 2 buckets (lives or dies) in one round of testing…likewise 2 pigs can test 2**2 buckets…or 2**n more generally. So we keep increasing n until we reach or exceed buckets. If more tests are permitted (minutesToTest//minutesToDie) we increase the base.

review
hard