[Challenge] Comparative Weights ⚖️

challenge

#1

Code Challenge #18: August 9, 2017

Every week, we feature the type of brain-teasing question that might be asked in a full-stack developer’s job interview at places such as Google and Facebook.

This week’s challenge was reported to have been asked in interviews at Microsoft:


The Challenge

Suppose you were given eight soccer balls (aka footballs :soccer:️), all of them seemingly identical. You are given a balance scale :balance_scale:️ and told that one of the eight balls is slightly heavier than the others (outlierBall). What’s the fewest number of times you have to use the scale to find outlierBall? Write a function, scaleOfTruth, that will determine the minimum number of weighs that you’ll need to find outlierBall.

  • Function Name: scaleOfTruth
  • Input: None
  • Output: an integer representing the minimum number of weighs needed to find outlierBall
  • Seven of the footballs have an exactly even weight, only one of the footballs (outlierBall) has a greater weight.
  • The balance scale is the only way that you can discern any physical difference between the eight footballs.
    • The balance scale did not come with any reference weights – the only weights you have to use on the balance scale are the footballs themselves.
    • The balance scale is very large – you can fit all eight balls on one side of the scale! Thus, you can put multiple footballs on each side when you weigh, if you so choose.
  • What if you were given a ninth football with an identical weight to the eight equally heavy balls you have already? What if outlierBall was lighter than all the others rather than heavier? Try to write your code so that it is easily maintainable and can be adapted to modifications in the interviewer’s questioning.
  • Always remember to explain your code and the thought processes behind it!
Find out more about basic challenges.

Hard Difficulty

Write a function, scaleOfTruthN that will solve this challenge with any given number of balls, n, and make sure that your function is as efficient as possible.

  • This function should print out the minimum number of weighs needed to find the outlierBall in a set of n footballs, where all balls have identical weights apart from one outlierBall, which is heavier.
  • Function Name: scaleOfTruthN
  • Input: n - an integer representing the number of footballs
  • Output: An integer representing the minium number of weighs to find the outlier ball.
  • Don’t forget to explain your submission just as you would do in a job interview setting!
Find out more about hard challenges and Big O

Reply to this thread with a link to your code on repl.it and paste your properly formatted code to participate! Don’t just submit your code, remember to explain your solution, too! If you want to be considered as the winner, your function must have the correct name and provide output in the format specified above, you also need to abide by our other simple rules.

As always solutions using imports to do all the heavy lifting such as itertools will not be considered for the winner.

When including your repl.it link, please just give us the link and not the code preview! Just put a space before your URL so that the preview box doesn’t show – too many preview boxes can make the thread hard to read.


The fine print:

Click the links to find out more about:


Essential Information on Code Challenges
#2

Can you put multiple footballs on each pan of the scale, so for example have 4 footballs on one pan and 4 on the other?


#3

It’s a very large balance scale – yes!


#4

Separate the balls in 3 groups. Compare 2 of them. If one of the groups has bigger weight, the outlierBall is there, if not, the outlierBall is in the group that’s not being measured. Repeat.

In case of x leftovers:
x == 1 -> add leftover to the group that’s not being measured
x == 2 -> add one to each of the groups being measured

C :

#include <stdlib.h>
#include <stdio.h>
#include <math.h>

int main(){
	printf("%d\n", scaleOfTruthN(8));
	return 0;
}

int scaleOfTruthN(int nBalls){
	int outlierBall = 0;
	int bal, out, extra;
	

	while(nBalls > 1){
		bal = out = floor(nBalls/3);
		extra = fmod(nBalls, 3);
		
		if(extra == 1) out++;
		else if(extra == 2) bal++;

		if(bal > out) nBalls = bal;
		else nBalls = out;

		outlierBall++;
	}

	return outlierBall;
}

#5

https://repl.it/KDpT/1

Reminds me of a binary search. So weigh an even amount of footballs on each side of the scale (n/2 where n is the number of fotballs). If there is an odd number, pick at random to put to the side. Each time you find the heavier set, split that set into 2. Repeat that process until there is only one ball on each side.

My solution does not work if n is less than 2.

class Main{
/*
Reminds me of a binary search.  So weigh an even amount of footballs on each side of the scale (n/2 where n is the number of fotballs).  If there is an odd number, pick at random to put to the side.   Each time you find the heavier set, split that set into 2.  Repeat that process until there is only one ball on each side.  Since you are looking for the minimum number, you do not need to go back and check to see if the outlier is heavier or lighter.

This solution is questionable around n < 2
*/
  public static int scaleOfTruthN(int numberOfFootballs){
    int whatsLeft = numberOfFootballs / 2;
    if( whatsLeft > 1 ){
      return 1 + numberOfFootballs % 2 + scaleOfTruthN(whatsLeft);  
    }else{
      return 1 + numberOfFootballs % 2;
    }
  }
  
  public static void main(String[] args){
    int numberOfFootballs = 9;
    if( args.length > 0 )
     numberOfFootballs = Integer.parseInt(args[0]);
    int value = scaleOfTruthN(numberOfFootballs);
    System.out.println("" + value);
  }
}

#6

Could make it harder by stating that the outlier ball can be heavier or lighter weight.


#7

Divide all available balls in two groups and weight one of them. After that you will know in which group the outlierball is.
You will do that until you have a group of two balls and then you will finally know which ball is the outlier.

JS:

function scaleOfTruthN (n) {
	if (n === 1) return 0;
	if (n % 2 === 0) {return 1 + scaleOfTruthN(n/2)};
	return scaleOfTruthN(n+1);
}

#8

I’m thinking this one through without reading any literature on the problem so as to keep a clear head. Here are my thoughts on the problem (though I won’t be competing in this event).

=begin
9 balls. Take one out.
Place four balls on each side of the scale.
if the scale tips, the heavier ball is on that side. 
If not, the heavy ball is the one left out.
If the scale tips, then discard the unused ball and
all the balls on the light side.
Now we have only four balls. 
Put two on one side, two on the other. 
Discard the balls from the light side.
One ball on each side will find the heaviest.
=end
balls = Array.new(9) { |x| x = 0 }
balls[rand(9)] = 1
puts balls
hold = balls.slice(4)
left = balls.slice(0, 4)
rght = balls.slice(5, 4)
puts "#{hold}, #{left}, #{rght} -> #{left == rght}" 
0
0
0
0
1
0
0
0
0
1, [0, 0, 0, 0], [0, 0, 0, 0] -> true

#9

Hard difficulty - I’ve divided the group into threes which are weighed against each other. This is the first challenge I’ve participated in and I’m not sure if I’m along the right lines, everyone else has gone for dividing the group in half or three.
https://repl.it/KE7r


#10

Correction: Considering a Balance scale (i.e. you can weight two groups at the same time), this is my new solution
You will divide all balls in three groups and weight two of them. After that you will know exactly which one of those three contains the outlier.
If there is one extra ball (remainder from division by 3), next iteration: balls+1 (not weighted group)
If there are two extra balls, this iteration should have an extra ball (on each weighted group)

JS:

function scaleOfTruthN (n) {
    if (n <= 1) return 0;
    let count = 0, r;
    while (n >= 3) {
      let m = Math.floor(n/3);
      r = n % 3;
      if (r === 2) {n++; continue}
      n = m + r;
      count++;
    }
    if (n >= 2) {count++}
    return count;
}

#11

https://repl.it/KEh1/0

My code is very simple. If the number of balls happens to be even, half the number each time until the remainder is 1 (the outlier). Odd numbers pose a different issue…

ScaleOfTruthN operates on this basis for odd numbers of balls (n)

  1. Remove a random ball and split the remainder on the scale - if the scale is balanced this would result in only one weigh being neccesary, but this relies on randomness. This means that the minimum number of ways could be 1, but I don’t think this is the desired outcome.

  2. Building off of above - if a random ball is removed and the remainder placed on the scale and it is not balanced, we know that the random ball is of the same weight of those other than the outliers and it is not needed to weigh it. Therefore if N is odd then the answer is the same as (N - 1).


#12

Tiene sentido

  • Según tu lógica necesitarías usar la balanza :balanza: solo 2 veces

#13

On every step I split the set that contains the outlier ball in 3 parts almost equal, i.e. 2 of the same size and one equal or with one more or less than the others​. I put on the balance the two equal partitions, each on a different side of balance. Three events can happen:

  1. (>) Left side to weight more than the right.
  2. (=) Both sides to be equal.
  3. (<) Right side to weight more than the left.
    Every one shows the partition with the outlier ball.
    If the the number of balls is n>0. For n=1 I need 0 times to use the scale
    For n between 2 and 3, I need 1 time of use
    For n between 4 and 9, I need at most 2 times to use the scale.
scaleOfTruthN= n=> Math.ceil(Math.log(n)/Math.log(3)-4e-15);

https://repl.it/KEsW/2


#14

We can assume that there is one and only one football that is heavier.
Regardless of the total number of football’s, it only makes sense to weigh an equal quantity in the left and right pans of the scale.
Let’s examine the case of eight football’s first.
We could start by weighing one football in each pan.
If the scale is unbalanced, then we are done. We know the heavier outlierBall , best case.
If the scale is balanced, then we can discard the two normal football’s we just weighed.
Now we can repeat this process with two previously unmeasured footballs.
We might need as many as four measurements to discover the outlierBall, worst case.
Maybe we can do better than this.
We could measure four football’s in each pan, then discard the lighter group of four.
The heavier group of four must contain the outlierBall. We take this group and divide it in half.
Now compare two football’s against two football’s, discard the lighter pair and keep the heavier.
Now we can compare these last two against each other, as one of them must be the outlierBall.
So, we have performed three weighings, this is the best case and the worst case using this method.
But maybe we can do better yet. Let start by placing three football’s in each pan, setting two aside.
If the scale balances, then we know that the outlierBall is in the group of two we had set aside.
It is a simple matter to compare those two, by weighing, to determine which is the outlierBall.
If the scale was unbalanced when we weighed three against three, then we know which group of three contains the outlierBall.
We Now take one football from this group and compare it with another football from this group.
If the scale balances, then the third football of that group must be the outlierBall.
If the scale is unbalanced, then we also know which is the outlierBall.
This method has a worst case of two measurements, an improvement over the previous method.
It turns out that if we started with nine balls, and put three in each pan and set three aside that the first measurement tells us which of the three groups contains the outlierBall and on additional measurement allows us to determine the outlierBall.
Now if we notice the similarities between the case of eight football’s and nine football’s.
The first thing we did was divide the football’s into three groups, as similar in size as possible.
It turns out that if we do this for any quantity, at least two of these groups will have the same size.
We can start by comparing the weight of two of the same sized groups and based on that result we now know which group contains the outlierBall AND that group is approximately one third the size.
We can repeat the process, eliminating about two thirds of the candidates at each step, until we have found the outlierBall.
We can construct a small table to make this clearer.

N, number of footballs; M, number of steps; L, football’s in the left pan; R, football’s in the right pan; S, football’s set aside.

N	M	L	R	S
1	0	0	0	0
2	1	1	1	0
3	1	1	1	1
4	2	1	1	2
5	2	2	2	1
6	2	2	2	2
7	2	2	2	3
8	2	3	3	2
9	2	3	3	3
10	3	3	3	4
11	3	4	4	3
12	3	4	4	4

We always place equal quantities in the left and right pans.
Then we recurse with which ever group holds the outlierBall.
But worst case analysis uses the largest group.
Here M, represents the total for that N; one for the starting row plus one for each additional row as we iterate/recurse using smaller groups.
Notice N is always less than or equal to 3^M.
Thus the logarithm of N, base three is always less than or equal to M. The ceiling rounds up to the next integer.
If we take the ceiling of the logarithm of N, base three; that is exactly M.
That is how I implemented my submission in Python 3.
Here is my code:

from math import log, ceil

def scaleOfTruth( ):
    return ceil(log(8, 3))

# the minimum numbers of weighs to find the heavy one
def scaleOfTruthN( n ):
    return ceil(log(n, 3))

print("scaleOfTruth( )=", scaleOfTruth( ) )

# 9 is 3^2, 27 is 3^3, 81 is 3^4, 243 is 3^5
for x in 8, 9, 10, 26, 27, 28, 80, 81, 82, 242, 243, 244:
    print("scaleOfTruthN(", x, ")=", scaleOfTruthN( x ))

And the corresponding output:

scaleOfTruth( )= 2
scaleOfTruthN( 8 )= 2
scaleOfTruthN( 9 )= 2
scaleOfTruthN( 10 )= 3
scaleOfTruthN( 26 )= 3
scaleOfTruthN( 27 )= 3
scaleOfTruthN( 28 )= 4
scaleOfTruthN( 80 )= 4
scaleOfTruthN( 81 )= 4
scaleOfTruthN( 82 )= 5
scaleOfTruthN( 242 )= 5
scaleOfTruthN( 243 )= 5
scaleOfTruthN( 244 )= 6

Here is the link:
https://repl.it/KFEy/20


#17

What is the purpose of “-4e-15”? Is that a typo?


#18

For n=9 I get 3 not 2 without that little substraction because Math.log(9)/Math.log(3)>2. I did an empirical error correction. Check also for n=3**24.


#19

You might not have that problem if you used a different logarithm.
Probably difficult to get an exact value using a natural logarithm.

Math.log2(9)/Math.log2(3)

or

Math.log10(9)/Math.log10(3)

#20

I ran 3**23 through all three logarithms:

Babel Compiler v6.4.4
Copyright (c) 2014-2015 Sebastian McKenzie
   Math.log(3**23)/Math.log(3)
=> 23.000000000000004
   Math.log2(3**23)/Math.log2(3)
=> 23
   Math.log10(3**23)/Math.log10(3)
=> 23

#21

Here is my solution

def scaleOfTruthN(n):
  weighs = [0 for x in range(0,n+1)]
  
  weighs[0]=0
  weighs[1]=0
  weighs[2]=1
  solu=0
  soluPrev=0

  for b in range(3,n+1):
    for v in range(1,int(n/2)+1):
      if b-2*v<0:
        break
      
      unbal=1+weighs[v]
      bal=1+weighs[b-2*v]
      if v==1:
        solu = max(bal,unbal)
      else:
        solu = min(soluPrev,max(bal,unbal))
        
      soluPrev = solu
  
    weighs[b]=solu
  return weighs[n]

print("weighs required =",scaleOfTruthN(8))

Full code and explanation can be found in the link.

https://repl.it/KJdC/19


#22

My solution in Javascript.
replit
An array of seven equal numbers and one bigger number is representing the footballs.
I sliced the array in two halves.
I took the sum of each one by reducing each (sliced) array, and then compared them.
A counter variable is updated at this point.
I keep the bigger (heavier) array and repeat recursively until the length of the remained array is 1.
This is the outlierBall.
Finally i return the counter.