Smallest number of voters given two halves

Question

One of my former students sent me a message about this interview, which he received by applying for a job as a junior developer.

There are two candidates running for president in the manner of class elections. Given two percent of voters, find out the smallest possible number of voters in a class.

Examples:

Entrance: 50.00, 50.00
Output: 2

Entrance: 25.00, 75.00
Output: 4

Entrance: 53.23, 46.77
Exit: 124 // First value, 1138 was wrong. Thanks Loïc for the right value

Note. The sum of input percent is always 100.00%, two decimal places

The last example made me scratch my head. This was the first time I heard about this problem, and I do not understand how to solve it.

EDIT: I called my student on this issue and said that he is not sure about the latter meaning. He said, and I quote: “It was an absurdly big issue” :( sorry, I had to research more before publishing it online. I assume that 9,797 is the result from the last example, though ..

Answer 1

You can calculate these values ​​using the best rational approximations as a percentage of voters. Wikipedia describes how to get these values ​​from the continued fraction (which can be calculated using the Euclidean algorithm ). The desired result is the first approximation, which is within 0.005% of the expected value.

Here is 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 additional values ​​before the 3rd and 4th converging is because their last terms (7 and 4, respectively) are greater than 1, so we need to check the approximation with decreasing last term.

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

An implementation of the Ruby example is available here (using the formulas from the Wikipedia page here , so it is slightly different from the above example).

Answer 2

You may notice at first that the trivial solution is to have 10,000 voters. Now try to find something below this.

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

Always select a minimum of two percent 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((Nj)/N) = 53.23 return N 

---

For the third example:

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

but

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

It can't be 1138 ...

But it works 62:

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

Rounded it gives you good values.

Answer 3

(After a few detailed changes :)

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

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

If you have 3 voters, 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 should have at least 4 people (so you can make 1/4, since 1/2 and 1/3 will not cut it). You can do this with a larger one (i.e. 2/8 = 25%), but the problem requires the smallest value.

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

 2/5 = 40% 

Since you cannot get this with anything other than 2 or more in the numerator (1 / x will never cut it off).

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

i.e. if you have a percentage of 3%, checking decisions all the way 96/99, 97/99, 98/99 before even getting to x / 100 is a waste of time. Instead, you can increase the numerator or denominator based on how well your current assumption is fulfilled (more or less)

 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 } 

A step-by-step example for finding a denominator that can give 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 good thing about this method is that it only takes steps (i + j) , where i is the numerator and j is the denominator.

Answer 4

I do not see the correspondence of this question to the position of a junior developer.

Answer 5

Then the answer that jumped into my head was more rude. There can be no more than 5001 unique answers, as 5001 unique numbers are between 00.00 and 50.00. Therefore, why not create and save a lookup table. Obviously, there will not be 5001 unique answers, because some answers will be repeated. The fact is that there are only 5001 valid fractions, because we round up 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 just viewing the table.

FWIW I understand that the Euclidean solution is "right." But I NEVER came up with this interview in the middle. However, I would know that this is possible, but I will not be able to push it in place.