Coding problem

Input: una lista non ordinata di numeri appartenenti ad un range definito [min, max] di cui uno mancante; la lunghezza della lista non è nota a priori
Output: il numero mancante

Scrivere un algoritmo - possibilmente O(N) in tempo e O(k) in spazio - che individui il numero mancante.

Esempio:
Input: {5, 4, 2, 6, 8, 3}
Output richiesto: 7

Have fun!

-quack

Potrebbero interessarti anche:

Pubblicato lunedì 23 aprile 2007 alle 1:53 AM

Commenti (10):
1. ilSilente
lunedì 23 aprile 2007 alle 8:16 PM - unknown unknown unknown
   
Scusa se N è la dimensione del problema k cos'è? Il num mancante?
   

Permalink - Rispondi al commento

2. Paperino
lunedì 23 aprile 2007 alle 8:22 PM - unknown unknown unknown
   

O(k) in spazio = occupazione di spazio (memoria) ragionevolmente costante e non dipendente dalla lunghezza dell'array in input. N è la grandezza dell'array.

   

Permalink - Rispondi al commento

3. Ampere73
lunedì 23 aprile 2007 alle 10:57 PM - unknown unknown unknown
   

mah...proviamoci...

mi sembra troppo incasinata come soluzione, non scriverò in C....però come tu mi insegni non è linguaggio che fa un algoritmo ;-) ma anche una ricetta è un algoritmo :-)

P.S. l'algoritmo prevede la presenza nel vettore del numero minimo (il che mi sembra pure logico ;) )

1) scorri il vettore e fai la somma di tutti i numeri nel vettore (SOMMA) e conta quanti sono (chiamo n il numero di elementi nel vettore) e trova il minimo (MIN); tutto può essere fatto con un unico scorrimento;

2) il numero mancante è dato (dovrebbe essere dato) da

  NUM_MANCANTE=SOMMA-(n+1)*(MIN+n/2)

Se è quella giusta......vinco un viaggio colloquio di lavoro alla MS?

Se non fosse quella giusta, poi ti spiego pure come ci sono arrivato........diciamo, geometricamente, visto che la mia memoria è pressocchè nulla.

ciao ciao,

ora posso andare a dormire

   

Permalink - Rispondi al commento

4. Luca
martedì 24 aprile 2007 alle 1:35 AM - unknown unknown unknown
   
Ci provo: Function TrovaNumero(ByVal numeri() As Integer) As Integer ' qui andrebbe un controllo sulla lunghezza dell'array, deve essere >1 Dim somma As Long Dim min As Integer = numeri(0) Dim max As Integer = numeri(0) For Each numero As Integer In numeri somma += numero If numero < min Then min = numero Else If numero > max Then max = numero Next Return (min + max) * (max - min + 1) / 2 - somma ' sono sicuro che si tratta di un intero perché ' se min + max è pari allora il prodotto (min + max) * (max - min + 1) è pari e divisibile per due ' se min + max è dispari allora max - min + 1 è pari ed il prodotto è divisibile per due ' (per andare da un numero pari a uno dispari ci vuole un numero pari di numeri, così come per andare da uno dispari ad un pari) End Function N iterazioni (se ne può risparmiare forse una) e K=3, 2 interi (min e max) e un long (somma) Sono assunto? ;-) P.S.: sorry per il vb :-)
   

Permalink - Rispondi al commento

5. Paperino
martedì 24 aprile 2007 alle 3:35 AM - unknown unknown unknown
   

Cominciano ad arrivare soluzioni corrette. Domenica posto tutto (paperino lo spoiler umano) Big Smile

   

Permalink - Rispondi al commento

6. Blackstorm
martedì 24 aprile 2007 alle 4:07 AM - unknown unknown unknown
   
Allora, l'idea che mi viene è questa: 1. Scorro l'array. 2. Memorizzo massimo(max), minimo(min) e una variabile somma(sum) dove mentre scorro sommo tutto l'array. 3. Dato che io so calcolare la somma dei numeri naturali da 1 ad n S(n)=((n)*(n+1)/2) mi calcolo la differenza fra S(min) e S(max), D=S(max)-S(min). 4.L'output è D-Sum. Just for fun: int missed(int a[], int lenght) { int min=a[0], max=[lenght-1], sum=0; for(int i=0; i; min=(aIdea:; max=(aIdea>max)?aIdea:; } int smin=((min*(min+1))/2); int smax=((max*(max+1))/2); int diff=smax-smin; return diff-sum; } ... che bello, mi ricordo ancora qualcosa... non mi picchiare se ho sbagliato il codice sono secoli che nn programmo... la soluzione dovrebbe essere giusta, perché la differenza fra la somma 1 a n e la somma da 1 a m dovrebbe dare la somma da n a m, e siccome manca un unico numero, deve essere la differenza fra la somma da n a m e la somma degli elementi dell'array... PS: si, è in c++... il mio primo amore :D
   

Permalink - Rispondi al commento

7. Beppe
martedì 24 aprile 2007 alle 9:32 PM - unknown unknown unknown
   
Con questa soluzione ho usato solo una variabile totale e usando solo 1 ciclo for. Ho ridotto finche' ho potuto, di piu' non so. protected int searchnumber(List lista) { int i = 0; int totale=0; int min=lista[0]; int max=lista[0]; foreach (int numero in lista) { i++; totale = totale + i - numero; if (numero < min) min = numero; if (numero > max) max = numero; } i++; return (totale + i * min); }
   

Permalink - Rispondi al commento

8. Filippo
mercoledì 25 aprile 2007 alle 2:37 AM - unknown unknown unknown
   
Vale anche un programmino in Perl da uno che lo conosce appena? :-) Conosco solo il Perl e neanche tanto bene... quindi non so quanta memoria occupi questo programma e se dipende dalla lunghezza dell'array anche se ho il vago sospetto che N possa essere troppo grande... Non so! In ogni caso io ci ho provato e per una lista breve come quella dell'esempio il programma funziona! :-D while ($cifra=<>) { #chop $cifra; (dipende dal file) $somma=$somma+$cifra; $max=$cifra if ($cifra>$max); if ($m++){ $min=$cifra if ($cifra<$min); } else { $min=$cifra; } } @lista2=($min .. $max); foreach $cifra2 (@lista2) { $somma2=$somma2+$cifra2; } $risultato=$somma2-$somma; print qq|$risultato\n|; Ciao!! P.S.: hai scritto a quelli dei test informatici per la traduzione in italiano?
   

Permalink - Rispondi al commento

9. ampere73
domenica 13 maggio 2007 alle 7:33 AM - unknown unknown unknown
   
allora Paperino? la soluzione da postare DOMENICA dove è? :-) ;-) e che c'ho il computer a tempo, tipo il film SPEED al contrario...cioè il portatile non può superare un certo numero di MINUTI di accensione continuata con velocità di processore alta, prima che automaticamete di spenga. Quindi la mia lettura dei blog risulta a "mozzichi" e tempo limitata e mi ero perso tutte le altre preziose soluzioni arrivate... muuuuuuuuuuuuuuu muuuuuuuuuuuuuuuuuuuu
   

Permalink - Rispondi al commento

10. Blackstorm
domenica 13 maggio 2007 alle 4:44 PM - unknown unknown unknown
   
Beppe, scusami, ma non ho capito molto bene il tuo codice... mi potresti descrivere l'algoritmo a parole? Temo che mi sfugga il senso generale... specie l'ultima operazione non mi torna molto...
   

Permalink - Rispondi al commento

I commenti sono disabilitati per questo post. Grazie!