CODEWITHSUNDEEP
algorithmsearchcomparison
CaptainQuality
CaptainQuality

Reputation: 157

Algorithm challenge: Find the unique value in an array

Given an array of rubber balls, for example: all balls are equal weight except one. What is the most efficient way to find the ball that has the unique weight, and that would require the least amount of placing the balls on a scale?

Upvotes: 1

Views: 129

Answers (3)

IVlad
IVlad

Reputation: 43477

Let's do it for 8 balls:

Leave 2 out, and weigh 3 - 3: you know which group of 3 has the different ball, or you know that the one left out is different, in which case one more weighting will find it.

To find it from the 3, leave one out and weigh them 1 - 1. Again, you will find it no matter what, and we did it in 2 weightings, beating the binary search.

For 16, you can do it in 3:

Leave 6 out. Compare 5 - 5. If equal, we can find it from the ones left out in 2 weightings.

From the 5, we can find it by comparing 2 - 2 then 1 - 1.

In general, if we have 3^x <= n < 3^(x + 1) balls, then we can do it in x + 1, which I believe is optimal, but don't have a proof:

3^1 <= 8 < 3^2 => answer = 2
3^2 <= 16 < 3^3 => answer = 3

This is because we can always split the number of balls into 3 groups of size k, k, k; k, k, k + 1 or k, k + 1, k + 1, which can then be solved recursively faster than if you split it into just two halves.

I'm not sure if this is optimal, but it beats the classic binary search.

Upvotes: 0

MrGreen
MrGreen

Reputation: 499

I believe you meant you can only use a scale to know the distinct ball. The following is my solution.

You have 3 cases:

Case 0: if there is only `1` ball, then this is the desired ball.

Case 1: the number of balls is divisible by 3. 
        Divide the balls into 3 equal sets {1, 2, 3}.
        weigh 1 and 2 ==> if equal, recurse on 3
                          if not, weigh 1 and 3 ==> if equal recurse on 2
                                                    if not recurse on 1




Case 2: the number of balls leave a remainder of 1 when divided by 3. 
        Take one ball out, call that ball x.
        You want to check if x is the desired ball or not.
        Take 2 more balls, call them y and z.

        Weigh y and z ==> if equal, weigh x and y ==> if equal, x is not the desired ball. This is case 0 or 1 on the set of balls without x.
                                                      if not, x is the distinct ball
                          if not, weigh x and y ==> if equal, z is the distinct ball
                                                    if not, y is the distinct ball.



Case 3: the number of balls leave a remainder of 2 when divided by 3.
        Take two balls out, call them x and y.
        Take one more ball, call it z.

        weigh x and y ==> if equal, weigh x and z ==> if equal this is case 0 or 1 on the remaining balls without x and y.
                                                      if not, z is the distinct ball.
                          if not, weigh x and z ==> if equal, y is the distinct ball.
                                                    if not, x is the distinct ball.

Upvotes: 0

david tallon
david tallon

Reputation: 424

You can easily do it via Binary Search Algorithm which is O(logn). You simply divide the group of balls into two equal groups. Then pick a side and divide those. Weigh them. If the piles are equal, the ball is in the other pile. If they are unequal, you continue the process on these two piles. Pick one, split and weigh. You will eventually isolate the ball that is different.

Upvotes: 1

Related Questions