Nombre solitaire

Soit \(n\) un entier positif ou nul. On considère un tableau contenant \(2n+1\) nombres entiers :

  • \(n\) paires de nombres, toutes distinctes ;
  • \(1\) nombre « solitaire » qui n'apparaît qu'une seule fois dans le tableau.

Les nombres de chaque paire sont toujours à la suite l'un de l'autre dans le tableau.

Ces tableaux seront représentés par des list Python.

En prenant \(n = 3\), on a aura \(3\) paires d'entiers et \(1\) nombre solitaire :

Une liste contenant 3 paires et 1 nombre solitaire
# indices  0  1  2  3  4  5  6
nombres = [2, 2, 5, 6, 6, 4, 4]
#                ^

Le but de cet exercice est de déterminer efficacement la valeur du nombre solitaire.

Longs tableaux

Les tableaux utilisés dans les tests secrets sont longs : une recherche linéaire échouera.

De façon générale, dans les tests secrets, il est interdit de lire plus de la moitié des valeurs contenues dans le tableau.

Écrire la fonction solitaire qui prend en paramètre une liste décrivant un tableau tel que décrit ci-dessus et qui renvoie la valeur du nombre solitaire.

Exemple 
>>> solitaire([9])
9
>>> solitaire([6, 6, 9])
9
>>> solitaire([1, 1, 5, 6, 6])
5
>>> solitaire([2, 8, 8, 5, 5, 3, 3])
2

###(Dés-)Active le code après la ligne # Tests (insensible à la casse)
(Ctrl+I)
Entrer ou sortir du mode "deux colonnes"
(Alt+: ; Ctrl pour inverser les colonnes)
Entrer ou sortir du mode "plein écran"
(Esc)
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier
Évaluations restantes : 10/10

.128013s3o_8;bcdufvg/0ly n7apSr1-me(P2=4:+twk%i9][5h)6050j0C0K0v0O0q0b0s0i0q0v0b0b0G010K0O0w010406050b0k0B0B0v0y0r040x0d0q0k0:0d0t050o0`0|0~100^0w04191g051j0o1j1l1g0^0j0O0m0(0*0,0.0T0O0n0T0q1z0T0K0?050Z0h0q0C1u0+0-011y1A1C1A0K1I1K1G0K0h0d0j101H0y1h0K0T0(130b0w0v0t0.0F011M1w010l0#0C0t0v0B0C1G1.1:1^1O1{1K1~200?0a0s0E0y0d0w0d0b0O160t0s0X1,0y0y0C0i2l19230t1h0o1*2y0K1(1%1)0j250.1C0t1}2i1G1r1t0)1N2I0O2K0t1!1s1G0w2r1h2w2y2$0_1/2m2Q1_2V0y0}0q0?0s0z2v2*0@2)242,1O2.2:2=0F2^1:2`2w2H012 0v2;040s0c332x0^362}0.393b0s0H3f352*373l2=0S3p3h3r3j380d2/3a2=0V3w2{2+1v2~3B303c0u3G3i3J3k3L3D3c0f3P3y3R3A3C3m0P3X2|3Z3t040z0p3(3I2R3!3M0z2@1a2_3x3)3;3+0z323_343{3:2-3T3b0z3e413g3H3s460?0z3o4a3q3|453#4f3v4i434d4m3,3F4p4c3z3~3O4v3Q3}4e3,3W4A3Y4C4s0z3%4G4k3K4s0F3.4i1i2!192O2B0j2F370i1!211h4W1k4U2(4S4#0X2#4H1_0M0?0X0l3p4w3Z0L2=4`4B2-0l0?0b132k0!2r4 4;1O0=040D594N3k0?1V0C0v0k5f445b0?0U0I3w0s5u0s4{3}0?0O0e0X0h153p5w501O0d0?0G5F5x1_0B0O0?4R2$065v5G5a5h045A1{184i5W5g015J045L5%5N2~0h0?285n375c5e4S5H5Y5j5l5@3z5c0U3w5U5v5/0.4?040L1y1K5M5|385z5B0C5D0K6e5X5*0?020q0K0g5-2$5(5o5Y5!2T603Z5c5s4p5V5V6701690O4_5.6f0t6h5C5E6N6n5+0G6u2_6w3s6h5#6m5)5+0A6%6x015P4f6B3;6D5t6G6@6I692r0K0k0y5$6v6I6P045~5m5{6n5c0R6:2-6Q6j6S2(6f5c0Q646@5u716h5P1C0C75706f6V6+5^0?5`7f6n725A6R6l6T6(0?0J7v4x6#6A765)627J3Z5+0o0o7Q3;6.04405T656^6f6K6M7s7A7n0#0O7q7V1_5+0N7:1O7X7Z6Y6I6V6X346Z3z7X5S2_6I6=6F7k6H7%5z7)7{6O5i0v1J5k7r847g0?797N6,7B0e7o7.8j34850?7i7F6,7}7@5}8g1K5 8o7w048n7z5)8q8s7/8z375+7I8Q815Q3,7a5p040Q6E5T88887m5Z6i6k8C6o5,8.8N7-8P7*7G048T8^6,7_6?8(803Z690C0$0C8Y0.868%906G8*6z6 8d6U5K8;7,7p8u2x913;8S8.7X3^9a7$6n93959701993`9b9o4=8b9j738E8i9z789z8=9l9L8x8.8B8U3*8f8h8G8L6,9M8H7K8+8O9m3c7|7H9r8W9t8k778x8$9C9D668e8+6$9U9p9i9~7b9(8?9*7#8(6_0?940b969$6C0?9@429_9`7+8+7D9Sa08|6!a39Pa15I9-at0.9s3G0o4.0C2y2ZaC4V1s4X2B2D2z1Z1#2B9J2y4W0^0o0X0Z0#0b04.

###(Dés-)Active le code après la ligne # Tests (insensible à la casse)
(Ctrl+I)
Entrer ou sortir du mode "deux colonnes"
(Alt+: ; Ctrl pour inverser les colonnes)
Entrer ou sortir du mode "plein écran"
(Esc)
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier
Évaluations restantes : 10/10

.128013s3o_8;bcdufvg/0ly n7apSr1-me(P2=4:+twk%i9][5h)6050j0C0K0v0O0q0b0s0i0q0v0b0b0G010K0O0w010406050b0k0B0B0v0y0r040x0d0q0k0:0d0t050o0`0|0~100^0w04191g051j0o1j1l1g0^0j0O0m0(0*0,0.0T0O0n0T0q1z0T0K0?050Z0h0q0C1u0+0-011y1A1C1A0K1I1K1G0K0h0d0j101H0y1h0K0T0(130b0w0v0t0.0F011M1w010l0#0C0t0v0B0C1G1.1:1^1O1{1K1~200?0a0s0E0y0d0w0d0b0O160t0s0X1,0y0y0C0i2l19230t1h0o1*2y0K1(1%1)0j250.1C0t1}2i1G1r1t0)1N2I0O2K0t1!1s1G0w2r1h2w2y2$0_1/2m2Q1_2V0y0}0q0?0s0z2v2*0@2)242,1O2.2:2=0F2^1:2`2w2H012 0v2;040s0c332x0^362}0.393b0s0H3f352*373l2=0S3p3h3r3j380d2/3a2=0V3w2{2+1v2~3B303c0u3G3i3J3k3L3D3c0f3P3y3R3A3C3m0P3X2|3Z3t040z0p3(3I2R3!3M0z2@1a2_3x3)3;3+0z323_343{3:2-3T3b0z3e413g3H3s460?0z3o4a3q3|453#4f3v4i434d4m3,3F4p4c3z3~3O4v3Q3}4e3,3W4A3Y4C4s0z3%4G4k3K4s0F3.4i1i2!192O2B0j2F370i1!211h4W1k4U2(4S4#0X2#4H1_0M0?0X0l3p4w3Z0L2=4`4B2-0l0?0b132k0!2r4 4;1O0=040D594N3k0?1V0C0v0k5f445b0?0U0I3w0s5u0s4{3}0?0O0e0X0h153p5w501O0d0?0G5F5x1_0B0O0?4R2$065v5G5a5h045A1{184i5W5g015J045L5%5N2~0h0?285n375c5e4S5H5Y5j5l5@3z5c0U3w5U5v5/0.4?040L1y1K5M5|385z5B0C5D0K6e5X5*0?020q0K0g5-2$5(5o5Y5!2T603Z5c5s4p5V5V6701690O4_5.6f0t6h5C5E6N6n5+0G6u2_6w3s6h5#6m5)5+0A6%6x015P4f6B3;6D5t6G6@6I692r0K0k0y5$6v6I6P045~5m5{6n5c0R6:2-6Q6j6S2(6f5c0Q646@5u716h5P1C0C75706f6V6+5^0?5`7f6n725A6R6l6T6(0?0J7v4x6#6A765)627J3Z5+0o0o7Q3;6.04405T656^6f6K6M7s7A7n0#0O7q7V1_5+0N7:1O7X7Z6Y6I6V6X346Z3z7X5S2_6I6=6F7k6H7%5z7)7{6O5i0v1J5k7r847g0?797N6,7B0e7o7.8j34850?7i7F6,7}7@5}8g1K5 8o7w048n7z5)8q8s7/8z375+7I8Q815Q3,7a5p040Q6E5T88887m5Z6i6k8C6o5,8.8N7-8P7*7G048T8^6,7_6?8(803Z690C0$0C8Y0.868%906G8*6z6 8d6U5K8;7,7p8u2x913;8S8.7X3^9a7$6n93959701993`9b9o4=8b9j738E8i9z789z8=9l9L8x8.8B8U3*8f8h8G8L6,9M8H7K8+8O9m3c7|7H9r8W9t8k778x8$9C9D668e8+6$9U9p9i9~7b9(8?9*7#8(6_0?940b969$6C0?9@429_9`7+8+7D9Sa08|6!a39Pa15I9-at0.9s3G0o4.0C2y2ZaC4V1s4X2B2D2z1Z1#2B9J2y4W0^0o0X0Z0#0b04.

###(Dés-)Active le code après la ligne # Tests (insensible à la casse)
(Ctrl+I)
Entrer ou sortir du mode "deux colonnes"
(Alt+: ; Ctrl pour inverser les colonnes)
Entrer ou sortir du mode "plein écran"
(Esc)
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier
Évaluations restantes : 10/10

.128013s3o_8bcdufvg/0ly n7apSr1-me,(P2=4:+Ntwk%i9][5h)6050i0B0L0u0P0p0b0r0h0p0u0b0b0G010L0P0v010406050b0j0A0A0u0x0q040w0d0p0j0;0d0s050n0{0}0 110_0v041a1h051k0n1k1m1h0_0i0P0l0)0+0-0/0U0P0m0U0p1A0U0L0@050!0g0p0B1v0,0.011z1B1D1B0L1J1L1H0L0g0d0i111I0x1i0L0U0)140b0v0u0s0/0F011N1x010k0$0B0s0u0A0B1H1/1;1_1P1|1L1 210@0a0r0E0x0d0v0d0b0P170s0r0Y1-0x0x0B0h2m1a240s1i0n1+2z0L1)1(1*0i260/1D0s1~2j1H1s1u0*1O2J0P2L0s1#1t1H0v2s1i2x2z2%0`1:2n2R1`2W0x0~0p0@0r0y2w2+0^2*252-1P2/2;2?0F2_1;2{2x2I01300u2=040r0c342y0_372~0/3a3c0r0H3g362+383m2?0T3q3i3s3k390d2:3b2?0W3x2|2,1w2 3C313d0t3H3j3K3l3M3E3d0f3Q3z3S3B3D3n0Q3Y2}3!3u040y0o3)3J2S3#3N0y2^1b2`3y3*3=3,0y333`353|3;2.3U3c0y3f423h3I3t470@0y3p4b3r3}463$4g3w4j444e4n3-3G4q4d3A3 3P4w3R3~4f3-3X4B3Z4D4t0y3(4H4l3L4t0F3/4j1j2#1a2P2C0i2G380h1#221i4X1l4V2)4T4$0Y2$4I1`0N0@0Y0k3q4x3!0M2?4{4C2.0k0@0b142l0#2s504=1P0?040D5a4O3l0@1W0B0u0j5g455c0@0C3q0r4|3~0@0P0e0Y0g165o380d0@0G5D3A0N0h0@0K180B5I3!5d5s4j5u512 5x0e1|194T5W0/5F045H5$5b0/5K5M5O5Q3=5d0V0I3x0r5{5V5-014@040P4`5U5v2.5Y5A5C645%010d4~610b5t651P5/045N2L5=1`5d5_4q5|6t5}5h39670B5B0L6h6b5)5+2%6v5p0/0A0P0@4S2%066u5|6i5i615Z2U6C5~6E6X6w0s0g0@296o5q5e6*6T5k5m6-015@3x6P6R6b60626!6I6x6U686B6a6Y5G6F2`6H3t5Y5!6}5E0@0z7c3A6K4g6;6q5`6Q785J0@2s0L0j0x5#6G6S6 6/5n5,6w5d0S6;0s6y6A7k0@0R6@6t7x7G6U6K1D0B7A7w6D5G7g5R0@5f7B6~7P5y717Y3=5)0J7+666U7b7$386?736w5)0n0n7/1P7i04416O6^5{7x6{637V5~7(0e7R0P7T7~5(0@0O8g018082777x6E76357o3!806N2`7x7l6s7n865x888o6b7P7z7J047E7?4y5Y8d8f8M7Z047L7_6~8q8k8H0u1K5l7U8x6b7D7F8O0$8e8%8s8p0@7.8V38803_2)8)7K6r6O7n6u8C047r7t7v8F8a54560!0P598R5?7!8+048I9e6p5r8Y8,7S8/2y8t7,8=8k8m8J5T896#7a6W9k6+0V7m6Q920B0%5P9D0/8z8 906_5~60947u9n04551D9b9d8{5~5d7#9$9A9i8!1L6:9M6=9m8@8N706z699*6~5S9W5y8P9q3d8;048?9z6~8_8J9F8A856`0@9J0b9L9{7@0@8~3{90926|9?3+5j9-8$8J8Lai9@9 8-8Qax8S8Ua67d5*8r9r7Oas8#9/aC9f8K9haz9p8k7-9v6L3-8J0Ral439Q9R6w9T0Z959W9Y579cah8(9%9g9:8ZaMa18y9=aFay5z9_72aO9l049y979+aS8.a99G91ad04afa;35a|04a#3ha%ac9S7qa+9Vaq5w9X9a58bh2ybj9)a=9+9jb36+b68:8G9obabt1`aVbM7 aX8`bC9|a}b77%9B96bi8|04aa6O1a4/0B2z2!b+4W1t4Y2C2E2A1!1$2Cat2z4X0_0n0Y9b0%04.

###(Dés-)Active le code après la ligne # Tests (insensible à la casse)
(Ctrl+I)
Entrer ou sortir du mode "deux colonnes"
(Alt+: ; Ctrl pour inverser les colonnes)
Entrer ou sortir du mode "plein écran"
(Esc)
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier
Évaluations restantes : 10/10

.128013s3o8bcdufvg/ly napSr1me,(P2=4tki9][5h)6050h0x0E0r0G0n0b0p0g0n0r0b0b0C010E0G0s010406050b0i0w0w0r0u0o040t0d0n0i0(0d0q050m0/0;0?0^0-0s041118051b0m1b1d180-0h0G0k0W0Y0!0$0L0G0l0L0n1r0L0E0+050R0f0n0x1m0Z0#011q1s1u1s0E1A1C1y0E0f0d0h0^1z0u190E0L0W0{0b0s0r0q0$0B011E1o010j0T0x0q0r0w0x1y1$1(1-1G1:1C1?1^0+0a0p0A0u0d0s0d0b0G0~0q0p0P1!0u0u0x0g2d111{0q190m1Y2q0E1W1V1X0h1}0$1u0q1=2a1y1j1l0X1F2A0G2C0q1S1k1y0s2j192o2q2U0.1%2e2I1.2N0u0=0n0+0v2n2Y0,2X1|2!1G2$2(0+0B2,1(2.2o2z012?0r2)040c2`2p0-2}2;0$30320D352q2R0x2q2G2t0h2x2~0g1S1_193j1c2S2/2p3e053o0P2T2Y2~0F0+1F0x0u0E3e0p3v2~0q0+0b0{2c0S2j3x381n1G0*040z0J3V3C39010w0G0+0H3%2:3X0$3Z0I0M3K3M3)0d0+0C0C3_3W2J3*3,043.122-373(3;013E043G3I404a423O043Q1u0R0G3U472{3`4b3Z3#3/2Z4b3+0+0N4x2~3Z0y4h3:424A044C4r3w411.4F4H4y4J44462W4P3Y0+3@4S2~3|043~4$3)4K4W484t424d4f3J4N043L4Y3a3P3R4o4q4X4i4Q0+4w4^4:1.4K2+564{014R4^4`521G594D3)5e2U5g4I58440K5k4u0+4G5f575i444M515p4Z045w5n5y0$4K5B2-5I5d4!3^5x5c4(4*5R5h5J5r3e495D0$4=0!3H4@5H5c4k4m3S4p0x5t424v3$5b5W432^5=535F4+4z440e5}5E5G2-5o4T5q0+635_5#5O5 5V6e4K5s6d6965604U0+6k5C6m3=5v6o6a33646u6g5+5`4K346l4E5P6w1G5T3 6h6t5{042_4^0-0m3z3h1a3u0m3s2r3l112u2t1R1T2t0r1B6W6Z1k2.6Z0Q0S0U04.
Aide

On peut tout d'abord constater que :

  • avant le nombre solitaire, le premier membre de chaque couple est à un indice pair et le second à un indice impair ;
  • après le nombre solitaire, le premier membre de chaque couple est à un indice impair et le second à un indice pair

Il est possible d'utiliser cette observation afin de mettre en place une méthode « Diviser pour régner » inspirée de la recherche dichotomique :

  • on définit une zone de recherche entre i_debut et i_fin ;
  • on calcule l'indice de la valeur du milieu de la zone de recherche ;
  • si l'indice du milieu est pair et que la valeur suivante est égale, le nombre solitaire se trouve plus loin ;
  • si l'indice du milieu est impair et que la valeur suivante est égale, le nombre solitaire se trouve avant ;
  • on ne détaille pas les deux autres cas de figure 😉