CODEWITHSUNDEEP
algorithmbinary-tree
jje
jje

Reputation: 21

Binary tree algorithm variation: How to conduct search if the each group can hold limited elements?

Consider exactly one out of n people carries a virus. The testing can be done with blood samples where small portions of people's blood are mixed together, but at most k people's blood can be mixed together. Also applying the test from the blood samples of k people cost k^(1/2)

The algorithm that I thought of is:

when n = 1 return the person 
First divide the groups into n/k, so that k people are in each group 
test each group  
if(group i contains a virus) 
   binary search(group i)

However, I don't know how to set k to minimize the total cost. I believe closer for k to be n will cost the minimum, but it is only my intuition without any evidence. Is there a more efficient algorithm that will cost the minimum?

Upvotes: 0

Views: 36

Answers (1)

Krishna Chaitanya
Krishna Chaitanya

Reputation: 225

The optimum way of minimizing test cost is arranging the group into a square, mix all the samples from each row into one sample, all the samples from each column into one sample and test them. Based on the result row & columns are identified and the specific sample can be identified.

if sqrt(n) < K

1 2 3
4 5 6
7 8 9

now total 6 samples R[1,2,3],R[4,5,6],R[7,8,9],C[1,4,7],C[2,5,8],C[3,6,9] and based on the result construct the result. If R1, R2 are positive and C1 & C2 are positive then all 1,2,4,5 are positive.

if sqrt(N) > K then divide N into N/K^2 groups of K^2 elements and do the same.

Upvotes: 1

Related Questions