Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>Here's a summary of <a href="https://stackoverflow.com/questions/3492302/easy-interview-question-got-harder-given-numbers-1-100-find-the-missing-number/3492664#3492664">Dimitris Andreou's</a> link.</p> <p>Remember sum of i-th powers, where i=1,2,..,k. This reduces the problem to solving the system of equations</p> <p>a<sub>1</sub> + a<sub>2</sub> + ... + a<sub>k</sub> = b<sub>1</sub></p> <p>a<sub>1</sub><sup>2</sup> + a<sub>2</sub><sup>2</sup> + ... + a<sub>k</sub><sup>2</sup> = b<sub>2</sub></p> <p>...</p> <p>a<sub>1</sub><sup>k</sup> + a<sub>2</sub><sup>k</sup> + ... + a<sub>k</sub><sup>k</sup> = b<sub>k</sub></p> <p>Using <a href="http://en.wikipedia.org/wiki/Newton_identities#Formulation_in_terms_of_symmetric_polynomials" rel="noreferrer">Newton's identities</a>, knowing b<sub>i</sub> allows to compute</p> <p>c<sub>1</sub> = a<sub>1</sub> + a<sub>2</sub> + ... a<sub>k</sub></p> <p>c<sub>2</sub> = a<sub>1</sub>a<sub>2</sub> + a<sub>1</sub>a<sub>3</sub> + ... + a<sub>k-1</sub>a<sub>k</sub></p> <p>...</p> <p>c<sub>k</sub> = a<sub>1</sub>a<sub>2</sub> ... a<sub>k</sub></p> <p>If you expand the polynomial (x-a<sub>1</sub>)...(x-a<sub>k</sub>) the coefficients will be exactly c<sub>1</sub>, ..., c<sub>k</sub> - see <a href="http://en.wikipedia.org/wiki/Vi%C3%A8te&#39;s_formulas" rel="noreferrer">Viète's formulas</a>. Since every polynomial factors uniquely (ring of polynomials is an <a href="http://en.wikipedia.org/wiki/Euclidean_domain" rel="noreferrer">Euclidean domain</a>), this means a<sub>i</sub> are uniquely determined, up to permutation.</p> <p>This ends a proof that remembering powers is enough to recover the numbers. For constant k, this is a good approach.</p> <p>However, when k is varying, the direct approach of computing c<sub>1</sub>,...,c<sub>k</sub> is prohibitely expensive, since e.g. c<sub>k</sub> is the product of all missing numbers, magnitude n!/(n-k)!. To overcome this, perform computations in Z<sub>q</sub> field, where q is a prime such that n &lt;= q &lt; 2n - it exists by <a href="http://en.wikipedia.org/wiki/Bertrand&#39;s_postulate" rel="noreferrer">Bertrand's postulate</a>. The proof doesn't need to be changed, since the formulas still hold, and factorization of polynomials is still unique. You also need an algorithm for factorization over finite fields, for example the one by <a href="http://en.wikipedia.org/wiki/Berlekamp&#39;s_algorithm" rel="noreferrer">Berlekamp</a> or <a href="http://en.wikipedia.org/wiki/Cantor%E2%80%93Zassenhaus_algorithm" rel="noreferrer">Cantor-Zassenhaus</a>.</p> <p>High level pseudocode for constant k:</p> <ul> <li>Compute i-th powers of given numbers</li> <li>Subtract to get sums of i-th powers of unknown numbers. Call the sums b<sub>i</sub>.</li> <li>Use Newton's identities to compute coefficients from b<sub>i</sub>; call them c<sub>i</sub>. Basically, c<sub>1</sub> = b<sub>1</sub>; c<sub>2</sub> = (c<sub>1</sub>b<sub>1</sub> - b<sub>2</sub>)/2; see Wikipedia for exact formulas</li> <li>Factor the polynomial x<sup>k</sup>-c<sub>1</sub>x<sup>k-1</sup> + ... + c<sub>k</sub>.</li> <li>The roots of the polynomial are the needed numbers a<sub>1</sub>, ..., a<sub>k</sub>.</li> </ul> <p>For varying k, find a prime n &lt;= q &lt; 2n using e.g. Miller-Rabin, and perform the steps with all numbers reduced modulo q.</p> <p>As Heinrich Apfelmus commented, instead of a prime q you can use q=2<sup>⌈log n⌉</sup> and perform <a href="http://en.wikipedia.org/wiki/Finite_field_arithmetic" rel="noreferrer">arithmetic in finite field</a>.</p>
    singulars
    1. This table or related slice is empty.
    1. POEasy interview question got harder: given numbers 1..100, find the missing number(s)
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USCommunity
    1. USsdcvvc
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. POEasy interview question got harder: given numbers 1..100, find the missing number(s)
      singulars
      1. PTQuestion
    1. This table or related slice is empty.
    1. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    1. COYou don't have to use a prime field, you can also use `q = 2^(log n)`. (How did you make the super- and subscripts?!)
      singulars
      1. PO
      1. USHeinrich Apfelmus
    2. COAlso, you can calculate the c_k on the fly, without using the power sums, thanks to the formula $c^{k+1}_m = c^k_{m+1} + c^k_m x_{k+1}$ where the superscript $k$ denotes the number of variables and $m$ the degree of the symmetric polynomial.
      singulars
      1. PO
      1. USHeinrich Apfelmus
    3. CO@Heinrich Apfelmus Thanks! I'm not sure about the power of two approach - in general factorization would be much tricker, since there are divisors of zero and no uniqueness. To make sub/superscripts in answers, HTML tags can be used, in comments I think it is not available.
      singulars
      1. PO
      1. USsdcvvc
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload