Least amount of voters, given two halves

One of my former students sent me a message about this interview question he got while applying for a job as a Junior Developer.

There are two candidates running for president in a mock classroom election. Given the two percentages of voters, find out the l开发者_如何学Ceast amount of possible voters in the classroom.

Examples:

Input: 50.00,50.00

Output: 2

Input: 25.00,75.00

Output: 4

Input: 53.23, 46.77

Output: 124 // The first value, 1138 was wrong. Thanks to Loïc for the correct value

Note: The sum of the input percentages are always 100.00%, two decimal places

The last example got me scratching my head. It was the first time I heard about this problem, and I'm kindof stumped on how to solve this.

EDIT: I called my student about the problem, and told me that he was not sure about the last value. He said, and I quote, "It was an absurdly large number output" :( sorry! I should've researched more before posting it online~ I'm guessing 9,797 is the output on the last example though..

You can compute these values by using the best rational approximations of the voter percentages. Wikipedia describes how to obtain these values from the continued fraction (which can be computed these using the euclidean algorithm). The desired result is the first approximation which is within 0.005% of the expected value.

Here's an example with 53.23%:

10000 = 1 * 5323 + 4677
5323  = 1 * 4677 + 646
4677  = 7 * 646  + 155
646   = 4 * 155  + 26
155   = 5 * 26   + 25
26    = 1 * 25   + 1
25    = 25* 1    + 0

Approximations:
1:   1 / 1
 -> 1 = 100%
2:   1 / (1 + 1/1) 
 -> 1/2 = 50%
2.5: 1 / (1 + 1 / (1 + 1/6))
 -> 7/1 = 53.75%
3:   1 / (1 + 1 / (1 + 1/7))
 -> 8/15 = 53.33%
3.5: 1 / (1 + 1 / (1 + 1 / (7 + 1/3)))
 -> 25/47 = 53.19%
4:   1 / (1 + 1 / (1 + 1 / (7 + 1/4)))
 -> 33/62 = 53.23%

The reason we have extra values before the 3rd and 4th convergents is that their last terms (7 and 4 respectively) are greater than 1, so we must test the approximation with the last term decremented.

The desired result is the denominator of the first value which rounds to the desired value, which in this vase is 62.

Sample Ruby implementation available here (using the formulae from the Wikipedia page here, so it looks slightly different to the above example).

First you can notice that a trivial solution is to have 10.000 voters. Now let's try to find something lower than that.

For each value of N starting à 1
  For Each value of i starting à 1
     If i/N = 46.77
       return N

Always choose the minimum of the two percentages to be faster.

Or faster :

For each value of N starting à 1
  i = floor(N*46.77/100)
  For j = i or i+1 
     If round(j/N) = 46.77 and round((N-j)/N) = 53.23
       return N

• 605/1138 = .5316344464
• (1138-605)/1138 = .4683655536

but

• 606/1138 = .5325131810
• (1138-606)/1138 = .4674868190

It can't be 1138...

But 62 is working :

• 33/62 = .5322580645
• (62-33)/62 = .4677419355

Rounded it's giving you the good values.

(After some extensive edits:)

If you only have 2 voters, then you can only generate the following percentages for candidates A and B:

0+100, 100+0, or 50+50

If you have 3 voters, then you have

0+100, 100+0, 33.33+66.67, 66.67+33.33 [notice the rounding]

So this is a fun problem about fractions.

If you can make 25% then you have to have at least 4 people (so you can do 1/4, since 1/2 and 1/3 won't cut it). You can do it with more (i.e. 2/8 = 25%) but the problem asks for the least.

However, more interesting fractions require numbers greater than 1 in the numerator:

2/5 = 40%

Since you can't get that with anything but a 2 or more in the numerator (1/x will never cut it).

You can compare at each step and increase either the numerator or denominator, which is much more efficient than iterating over the whole sample space for j and then incrementing i;

i.e. if you have a percentage of 3%, checking solutions all the way up in the fashion of 96/99, 97/99, 98/99 before even getting to x/100 is a waste of time. Instead, you can increment the numerator or denominator based on how well your current guess is doing (greater than or less than) like so

int max = 5000; //we only need to go half-way at most.

public int minVoters (double onePercentage) {

    double checkPercentage = onePercentage;
    if (onePercentage > 50.0)
        checkPercentage = 100-onePercentage; //get the smaller percentage value

    double i=1;
    double j=1; //arguments of Math.round must be double or float
    double temp = 0;

    while (j<max || i<max-1) { //we can go all the way to 4999/5000 for the lesser value

        temp = (i/j)*100;
        temp = Math.round(temp);
        temp = temp/100;

        if (temp == checkPercentage)
            return j;

        else if (temp > checkPercentage) //we passed up our value and need to increase the denominator
            j++;

        else if (temp < checkPercentage) //we are too low and increase the numerator
            i++;
    }

    return 0; //no such solution
}

Step-wise example for finding the denominator that can yield 55%

   55/100 = 11/20 

   100-55 = 45 = 9/20 (checkPercentage will be 45.0)


1/1 100.0%  
1/2 50.00%  
1/3 33.33%  
2/3 66.67%  
2/4 50.00%  
2/5 40.00%  
3/5 60.00%  
3/6 50.00%  
3/7 42.86%  (too low, increase numerator)  
4/7 57.14%  (too high, increase denominator)  
4/8 50.00%  
4/9 44.44%  
5/9 55.56%  
5/10 50.00%  
5/11 45.45%  
6/11 54.54%  
6/12 50.00%  
6/13 46.15%  
6/14 42.86%  
7/14 50.00%  
7/15 46.67%  
7/16 43.75%  
8/16 50.00%  
8/17 47.06%  
8/19 42.11%  
9/19 47.37%  
9/20 45.00% <-bingo

The nice thing about this method is that it will only take (i+j) steps where i is the numerator and j is the denominator.

I cannot see the relevance of this question to a position as junior developer.

Then answer that jumped into my head was more of a brute-force approach. There can be at most 5001 unique answers because there 5001 unique numbers between 00.00 and 50.00 . Consequently, why not create and save a look-up table. Obviously, there won't be 5001 unique answer because some answers will be repeated. The point is, there are only 5001 valid fractions because we are rounding to two digits.

int[] minPossible = new int[5001];
int numSolutionsFound = 0;
N = 2;
while(numSolutionsFound < 5001) {
  for(int i = 0 ; i <= N/2 ; i++) {
    //compute i/N 
    //see if the corresponding table entry is set 
    //if not write N there and increment numSolutionsFound   
  }
  N++;
}

//Save answer here

Now the solution is merely a table look up.

FWIW I realize the euclidean solution is "correct". But I'd NEVER come up with that mid interview. However, I'd know something like that was possible -- but I won't be able to whip it out on the spot.