somma a coppie di n numeri in ordine non crescente

Question

ho visto questa domanda in un programmazione interview blog.

Se somme a coppie di n numeri sono riportati in ordine decrescente non identificano i singoli numeri. Se la somma è danneggiata, stampa -1.

Esempio:

i/p: 4 5 7 10 12 13 

o/p: 1 3 4 9 

Un suggerimento sarebbe sufficiente.

Answer 1

Sia B essere l'elenco delle somme a coppie, con B[0] <= B[1] <= ... <= B[m-1] e lasciare A essere la lista originale dei numeri che stiamo cercando di trovare, con A[0] < A[1] < ... < A[n-1], dove m = n(n-1)/2.

Dato A[0], calcolare A in tempo polinomiale

Corporatura A dal elemento più piccolo al più grande. Supponiamo che sappiamo già A[0]. Quindi, poiché B[0] è l'elemento più piccolo in B, può sorgere solo come A[0] + A[1]. Allo stesso modo, B[1] deve essere uguale a A[0] + A[2]. Pertanto, se conosciamo A[0], possiamo calcolare A[1] e A[2].

Dopo questo, tuttavia, questo schema si interrompe. B[2] potrebbe essere A[0] + A[3] o A[1] + A[2] e senza conoscenza preliminare, non possiamo sapere quale sia. Tuttavia, se conosciamo A[0], possiamo calcolare A[1] e A[2] come descritto sopra, quindi rimuovere A[1] + A[2] da B. Il successivo elemento più piccolo è quindi garantito da A[0] + A[3], che ci consente di trovare A[3]. Continuando così, possiamo trovare tutto il A senza mai tornare indietro. L'algoritmo simile a questa:

for i from 1 to n-1 { 
    // REMOVE SEEN SUMS FROM B 
    for j from 0 to i-2 { 
     remove A[j]+A[i-1] from B 
    } 
    // SOLVE FOR NEXT TERM 
    A[i] = B[0] - A[0] 
} 
return A 

Ecco come funziona dal vostro esempio dove B = [4,5,7,10,12,13] se sappiamo A[0]=1:

start 
    B = [4,5,7,10,12,13] 
    A[0] = 1 

i=1: 
    B = [4,5,7,10,12,13] 
    A[1] = 4-1 = 3 

i=2: 
    Remove 1+3 from B 
    B = [5,7,10,12,13] 
    A[2] = 5-1 = 4 

i=3: 
    Remove 1+4 and 3+4 from B 
    B = [10,12,13] 
    A[3] = 10-1 = 9 

end 
    Remove 1+9 and 3+9 and 4+9 from B 
    B = [] 
    A = [1,3,4,9] 

Quindi tutto si riduce a conoscere A[0], da cui si può calcolare la resto di A.

Compute A[0] in tempo polinomiale

Ora possiamo semplicemente provare ogni possibilità di A[0]. Poiché sappiamo B[0] = A[0] + A[1], sappiamo che A[0] deve essere un numero intero compreso tra 0 e B[0]/2 - 1. Sappiamo anche che

B[0] = A[0] + A[1] 
B[1] = A[0] + A[2] 

Inoltre, c'è qualche indice i con 2 <= i <= n-1 tale che

B[i] = A[1] + A[2] 

Perché? Poiché le uniche voci potenzialmente più piccole di A[1]+A[2] hanno il formato A[0] + A[j] e ci sono al massimo n-1 tali espressioni. Pertanto sappiamo anche che

A[0] = (B[0]+B[1] - B[i])/2 

per alcuni 2 <= i <= n-1.Questo, insieme al fatto che 0129061-e B[0]/2-1 offre A[0] offre solo alcune possibilità per il test A[0].

Per l'esempio, esistono due possibilità per A[0]: 0 o 1. Se cerchiamo l'algoritmo con A[0]=0, ecco cosa succede: approccio

start 
    B = [4,5,7,10,12,13] 
    A[0] = 0 

i=1: 
    B = [4,5,7,10,12,13] 
    A[1] = 4-0 = 4 

i=2: 
    Remove 0+4 from B 
    B = [5,7,10,12,13] 
    A[2] = 5-0 = 5 

i=3: 
    Remove 0+5 and 4+5 from B 
    B = !!! PROBLEM, THERE IS NO 9 IN B! 

end 

Answer 2

Non sono sicuro dell'algoritmo più veloce, ma posso spiegare come funziona.

Il primo numero della O/P, è la differenza tra la prima e la seconda i/p

5-4=1 

, così ora è necessario prima o/numero di p.

Il secondo numero di o/p è il primo I/P meno il primo o/p.

4-1=3 

terzo o/p è seconda o/p minus prima i/p

5-1=4 

Answer 3

Alcuni indizi:

• La dimensione dell'input è N * (N- 1)/2, quindi è possibile dedurre la dimensione dell'output (ovvero 6 elementi nell'ingresso corrispondono a 4 elementi nell'output)

• La somma degli input è la somma dell'output divisa per N - 1 (ad es. 1+3+4+9 = (4+5+7+10+12+13)/(4-1))

• L'ingresso più basso e ingressi alte sono la somma dei due due uscite più basse e alte rispettivamente (cioè 4 = 1 + 3 e 13 = 4 + 9)

• all'ingresso successivo più basso (5) fa differisce di un solo addendo da il primo (1), quindi puoi calcolare uno degli addendi prendendo la differenza (5-1).

Answer 4

Ferdinand Beyer era sulla strada giusta, credo, prima che cancellasse la sua risposta. Per ripetere parte del suo approccio: hai quattro incognite, a, b, c e d con a ≤ b ≤ c ≤ d. Da questo, si può formare un ordinamento parziale di tutte le somme:

a + b ≤ a + c 
a + b ≤ a + d 
a + c ≤ b + c 
a + d ≤ b + d 
a + d ≤ c + d 
b + c ≤ b + d 
b + d ≤ c + d 

Se questo fosse un ordine totale, allora si dovrebbe conoscere ognuno dei sei valori a + b, a + c, a + d, b + c, b + d e c + d. Si potrebbe quindi seguire il piano originale di Ferdinand e risolvere facilmente le equazioni simultanee.

Sfortunatamente, c'è la coppia (a + d, b + c), che può essere ordinata in entrambi i modi.Ma questo è abbastanza facile da gestire: supponiamo che a + d < b + c (i valori di input siano tutti distinti, quindi non è necessario preoccuparsi di usare ≤) e provare a risolvere le equazioni simultanee. Quindi assumere b + c < a + d e ripetere. Se entrambi i gruppi di equazioni hanno una soluzione, il problema originale ha due risposte. Se nessuno dei due ha una soluzione, l'output dovrebbe essere -1. Altrimenti, hai la tua (unica) soluzione.

Answer 5

di PengOne al recupero di un dato A [0] e B è buono, ma c'è un modo migliore per calcolare A [0]. Si noti che i due più piccoli elementi di B sono:

B[0] = A[0] + A[1] 
B[1] = A[0] + A[2] 

e

B[i] = A[1] + A[2] 

per qualche i.

Pertanto,

A[0] = (B[0] + B[1] - B[i])/2 

per qualche i, e abbiamo semplicemente bisogno di provare O (n^{1/2}) possibilità, dal momento che è delimitata da O (n^{1/2}) e vedere se si conduce a un'impostazione valida dei restanti elementi di A per la soluzione di PengOne. Il tempo di esecuzione totale è O (n^{3/2}), dove n è il numero di numeri nell'input.

Answer 6

Recentemente stavo controllando domande di intervista e ho risolto il problema con l'aiuto di @ di PengOne suggerimento per la ricerca di primo valore,

Quindi, se qualcuno ha bisogno di una soluzione di lavoro completo: E 'in PHP:

complessità temporale: O ((n * (n-2)) + 3 + n) con variabili di supporto. complessità spaziale: quasi uguale alla complessità del tempo.

<?php 
function getSublistSize($length) 
{ 
    $i = 2; 
    $n = 0; 

    while ($i <= $length) { 
     if (is_int($length/$i)) { 
      if ($length == $i * ($i + 1)/2) { 
       return ($i + 1); 
      } 
     } 

     ++$i; 
    } 

    return $n; 
} 

function findSubstractList(array $list) 
{ 
    $length = count($list); 

    $n = getSublistSize($length); 
    $nth = $n - 1; 

    $substractList = []; 
    $substractTotal = array_sum($list)/($length/2); // A + B + C + D 

    /** 
    * formula : A = (list[0] + list[1] - list[nth -1])/2 
    * list[0] = A + B, 
    * list[1] = A + C, 
    * list[nth - 1] = B + C 
    * 
    * => ((A + B) + (A + C) - (B + C))/2 
    * => (A + A + (B + C - B - C))/2 
    * => (2A + 0)/2 => 2A/2 
    * => A 
    */ 
    $substractList[] = (($list[0] + $list[1]) - $list[$nth])/2; 

    for ($i = 0; $i < $nth; ++$i) { 
     $substractList[] = ($list[$i] - $substractList[0]); 
    } 

// $substractList[3] = $substractTotal - ($list[$nth - 1] + $substractList[0]); 


    return $substractList; 
} 


$list = [5, 8, 14, 28, 40, 11, 17, 31, 43, 20, 34, 46, 40, 52, 66]; 

print_r(findSubstractList($list)); 

/** 
* P) [6, 11, 101, 15, 105, 110]; 
* S) [1, 5, 10, 100] 
* 
* P) [5, 8, 14, 28, 40, 11, 17, 31, 43, 20, 34, 46, 40, 52, 66]; 
* S) [1, 4, 7, 13, 27, 39] 
* 
*/