Author: damleo

Editorial : Coyote and his balls

Problem Link : https://www.hackerrank.com/contests/da-iict-ipc-02-1/challenges/coyote-and-his-balls-p

Required Knowledge : naive logic

Explanation : There are 2 possible solutions to this problem but the logic in both is the same. Consider we have been given n balls. Now we do 1 comparison using weighing pan. Here we divide the balls into 3 parts which are approx 1/3rd of n.                For  3n balls – n,n,n ; for 3n+1 balls – n+1,n,n ;  for 3n+2 balls- n,n+1,n+1 . We compare the last 2 parts using weighing pan. If they are equal, then the non-identical ball lies in the 1st part. If they are not equal, the non-identical ball lies in the pan which was lighter of the two. So effectively we reduced the problem into 1/3rd its size. So if we go on doing this, we will require log n(base 3 ) – ceiling comparisons. This is one possible solution.                                                                                                                         The second possible solution is a recursive method. Let ans() be the recursive method. The two base cases are n=1 and n<=3 for which the answers are 0 and 1 respectively. For n%3==0 , we divide into 3 parts each having n/3 balls. Therefore we return  ans(n/3) + 1 . If n%3 !=0 in worst case we will have to look at (n/3)+1 balls. Hence we return ans(n/3 +1 ) +1 and not ans (n/3 ) +1.

Setter’s  solution: http://ideone.com/e.js/lgvYbc        (This one uses recursive method)

Tester’s Solution: https://www.hackerrank.com/contests/da-iict-ipc-02-1/challenges/coyote-and-his-balls-p/submissions/code/3630098                                          (This one uses log to base 3 method)

For any doubts feel free to contact me on 201401114@daiict.ac.in.