Algorithm challenge: Find the unique value in an array

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.

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.

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.