Le plus petit nombre de votants, compte tenu de deux moitiés.

Question

Un de mes anciens étudiants m'a envoyé un message à propos de cette question d'entretien qu'il a reçue alors qu'il postulait pour un emploi de développeur junior.

Deux candidats se présentent au poste de président lors d'une élection fictive en classe. Étant donné les deux pourcentages de votants, trouvez le plus petit nombre de votants possibles dans la classe.

Exemples :

Entrée : 50.00,50.00
Sortie : 2

Entrée : 25.00,75.00
Sortie : 4

Entrée : 53.23, 46.77
Sortie : 124 // La première valeur, 1138, était fausse. Merci à Loïc pour la valeur correcte

Remarque : la somme des pourcentages d'entrée est toujours de 100,00 %, avec deux décimales.

Le dernier exemple m'a fait me gratter la tête. C'est la première fois que j'entends parler de ce problème, et je suis un peu perplexe quant à la façon de le résoudre.

EDIT : J'ai appelé mon étudiant au sujet du problème, et il m'a dit qu'il n'était pas sûr de la dernière valeur. Il a dit, et je cite, "C'était une sortie de nombre absurdement grande" :( désolé ! J'aurais dû faire plus de recherches avant de le poster en ligne Je suppose que 9,797 est le résultat du dernier exemple

Answer 1

Vous pouvez calculer ces valeurs en utilisant la fonction les meilleures approximations rationnelles des pourcentages des électeurs. Wikipedia décrit comment obtenir ces valeurs à partir du fraction continue (qui peut être calculée en utilisant le algorithme euclidien ). Le résultat souhaité est la première approximation qui se situe à moins de 0,005% de la valeur attendue.

Voici un exemple avec 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%

La raison pour laquelle nous avons des valeurs supplémentaires avant les 3ème et 4ème convergents est que leurs derniers termes (7 et 4 respectivement) sont supérieurs à 1, nous devons donc tester l'approximation avec le dernier terme décrémenté.

Le résultat souhaité est le dénominateur de la première valeur qui s'arrondit à la valeur souhaitée, qui dans ce vase est 62.

Exemple d'implémentation Ruby disponible ici (en utilisant les formules de la page Wikipedia ici Il est donc légèrement différent de l'exemple ci-dessus).

Answer 2

Tout d'abord, vous pouvez remarquer qu'une solution triviale consiste à avoir 10 000 électeurs. Maintenant, essayons de trouver une solution inférieure à cela.

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

Choisissez toujours le minimum des deux pourcentages pour être plus rapide.

Ou plus rapidement :

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

---

Pour le troisième exemple :

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

mais

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

Ça ne peut pas être 1138...

Mais le 62 fonctionne :

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

Arrondi, il vous donne les bonnes valeurs.

Answer 3

(Après quelques modifications importantes :)

Si vous n'avez que 2 votants, vous ne pouvez générer que les pourcentages suivants pour les candidats A et B :

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

Si vous avez 3 votants, alors vous avez

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

C'est un problème amusant sur les fractions.

Si vous pouvez faire 25%, vous devez alors avoir au moins 4 personnes (vous pouvez donc faire 1/4, car 1/2 et 1/3 ne suffiront pas). Vous pouvez le faire avec plus (c'est-à-dire 2/8 = 25%) mais le problème demande le moins.

Cependant, des fractions plus intéressantes nécessitent des nombres supérieurs à 1 au numérateur :

2/5 = 40%

Puisque vous ne pouvez pas l'obtenir avec autre chose qu'un 2 ou plus au numérateur (1/x ne suffira jamais).

Vous pouvez comparer à chaque étape et augmenter soit le numérateur soit le dénominateur, ce qui est beaucoup plus efficace que d'itérer sur l'ensemble de l'espace d'échantillonnage pour j et d'incrémenter ensuite i ;

Par exemple, si vous avez un pourcentage de 3%, vérifier toutes les solutions à la manière de 96/99, 97/99, 98/99 avant même d'arriver à x/100 est une perte de temps. Au lieu de cela, vous pouvez incrémenter le numérateur ou le dénominateur en fonction du résultat de votre estimation actuelle (supérieur ou inférieur à), comme suit

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
}

Exemple pas à pas pour trouver le dénominateur qui peut donner 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

Ce qui est bien avec cette méthode, c'est qu'elle prend seulement (i+j) étapes où i est le numérateur et j est le dénominateur.

Answer 4

Je ne vois pas la pertinence de cette question pour un poste de développeur junior.

Answer 5

La réponse qui m'est venue à l'esprit était plutôt une approche de force brute. Il peut y avoir au maximum 5001 réponses uniques car il y a 5001 numéros uniques entre 00.00 et 50.00 . Par conséquent, pourquoi ne pas créer et sauvegarder une table de consultation. Évidemment, il n'y aura pas 5001 réponses uniques car certaines réponses seront répétées. Le fait est qu'il n'y a que 5001 fractions valides car nous arrondissons à deux chiffres.

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

Maintenant, la solution consiste simplement à consulter une table.

Pour info, je réalise que la solution euclidienne est "correcte". Mais je ne trouverais JAMAIS cette solution en plein entretien. Cependant, je saurais que quelque chose comme ça est possible - mais je ne serais pas capable de le sortir sur le champ.