You now have 8 Kinder Eggs and all of them have a toy inside. Each toy weighs (s

Question

You now have 8 Kinder Eggs and all of them have a toy inside. Each toy weighs (significantly) differently from the rest. You are told that two of the eggs have the same toy inside and all the rest of the eggs have different toys. Thus, there are 7 different toys in the 8 eggs. You are again given a balance, but this balance can only fit one egg on each side. You do not want to face the disappointment of opening up two eggs with the same toy inside so you need to find which two eggs have the same toy (you can give one of these to your younger sibling or friend). Answer the following:

a) Give an algorithm (pseudocode) to find the pair of eggs with the same toy inside.
b) What is the best case number of comparisons (each time you use the scale) needed to find the pair of eggs with the same toy with your algorithm?
c) What is the worst case number of comparisons needed to find the pair of eggs with the same toy with your algorithm?
d) What is the best and worst case number of comparisons needed to find the pair of eggs with the same toy with your algorithm if there were n eggs instead of just 8 (and still just one pair with the same toy inside)?

Explanation / Answer

a)

L={1,2,3,4,5,6,7,8}

Algorithm FindSameToys (A,L);

Input: An array of weights of eggs containing toys and array L containing indices of eggs to be searched.

Output: The indices of two eggs with same toys.

n=length of L

If n=2 then

                If A[L[0]]=A[L[1]] then

return (L[0],L[1])

f=first element in L

For each i in L - first element do

                compare A[f] with A[i]

                if A[f]=A[i] then

                return (f,i)

                else if A[f] > A[i] then

                                add i to lessweightlist

                else

                                add I to greaterweightlist

FindSameToys(A, lessweightlist)

FindSameToys(A, greaterweightlist)

b) The best case number of comparisons is 1. The best case will occur when two eggs first compared has the same toys.

c)The worst case number of comparisons is 28. The worst case will occur all the eggs are in sorted order and the eggs containing the same toys are present at the end of the array.

d)The best case number of comparisons is 1 for n eggs.

The worst case number of comparisons is n(n-1)/2

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.