Hero Image
- Mihai Surdeanu

Descoperă numărul lipsă

Pentru că ne place algoritmica, revenim cu o problemă relativ simplă: Se dă un array de numere, conținând exact n numere distincte din intervalul [0, n]. Se cere să se găsească numărul lipsă. Se garantează faptul că întotdeauna un singur număr va lipsi. Se consideră că n are tipul int.

Haideți să luăm și câteva exemple:

  • array = [4, 0, 1, 2]. Observăm că n = 4 și numărul lipsă este 3.
  • array = [0, 2, 4, 3, 5, 6]. Observăm că n = 6 și numărul lipsă este 1.

Să notăm cu X numărul lipsă. Dacă n = 4, vom avea numere din intervalul închis la ambele capete [0, 4], adică 0, 1, 2, 3, 4. Din școala generală ne aducem aminte că dacă le adunăm pe toate vom obține 10 = n x ( n + 1) / 2 = 4 x 5 / 2 = 10. Ni se garantează faptul că un singur număr lipsește și toate celelalte vor fi prezente în array-ul nostru. În acest condiții, putem să adunăm toate numerele din array, să determinăm valoarei lui n și să determinăm necunoscuta X ca fiind diferența între suma toturor numerelor de la 0 la n și suma obținută de noi.

Aplicând algoritmul de mai sus în cazul primului examplu vom avea:

  1. suma tuturor numerelor de la 0 la n (n = 4) ca fiind 10.
  2. suma tuturor numerelor din array-ul dat = 7.

Pasul următor este să facem diferența între 10 și 7 și vom avea fix numărul lipsă - 3. Soluția noastră va avea o complexitate de timp liniară și o complexitate de spațiu constantă. De ce? Pentru că trebuie să iterăm o dată peste toate valorile din lista primită ca și input și în plus nu avem nevoie de nicio structură de dată adițională de tipul List sau Map pentru stocarea unor date intermediare.

O altă idee de implementare este să sortăm lista de valori primită ca și input crescător. După ce am făcut sortarea, putem să iterăm peste valorile obținute și să determinăm ușor numărul care lipsește. Dacă ar fi să evaluăm această soluție, am ajunge la concluzia că are o complexitate de timp = O(nlogn), dată de algoritmul de sortare - quicksort și o complexitate spațială liniară - O(n) asta dacă nu ni se permite să modificăm lista inițială. Să zicem că lista inițială este imutabilă.

O altă idee este să folosim un HashSet pentru a stoca valorile din lista inițală. Prima fază este să inițializăm set-ul cu valorile din listă, după care să iterăm de la 0 la n și să căutăm elementul care nu se află în set. Analizarea acestei soluții ne conferă o complexitate de timp liniară și una de spațiu tot liniară.

Spor la implementare!

Related Posts:

Algoritm pentru planificarea optimă a unor pași dintr-un workflow

Algoritm pentru planificarea optimă a unor pași dintr-un workflow

Să spunem că vrei să implementezi un algoritm de planificare automată a unui set de pași, parte a unui workflow, în care fiecare pas poate depinde de unul sau mai mulți pași din acesta. Bineînțeles că algoritmul pe care dorim să îl implementăm, se dorește a fi cât mai optim, în așa fel încât să genereze cea mai bună variantă de planificare a tuturor pașilor (unii pași pot fi în paralel executați), în așa fel încât să se minimizeze timpul de rulare al întreg workflow-ului.

14th Nov 2020 - Mihai Surdeanu

Comments:

Blog Comments powered by Disqus.