Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>Theoretically,</p> <p>It is possible to do in O(1) space (in RAM model, i.e. O(1) words) and O(n) time even with a read-only array.</p> <blockquote> <p>Warning: Long post with some mathematics. If you are only interested in the code and not the algorithm/proof, skip to the code section. You would need to read some parts of the algorithm section to understand the code, though.</p> </blockquote> <hr> <p><strong>Algorithm</strong></p> <p>Assume the missing numbers are x and y.</p> <p>There are two possibilities for the array:</p> <blockquote> <p>1) One number is repeated three times, and the remaining numbers in the array appear exactly once.</p> </blockquote> <p>For this case, the bucketed XOR trick will work.</p> <p>Do a XOR of all elements of the array with 1,2,...,n.</p> <p>You end up with z = x XOR y.</p> <p>There is at least one bit of z which is non-zero.</p> <p>Now differentiating the elements of the array based on that bit (two buckets) do a XOR pass through the array again.</p> <p>You will end up with x and y.</p> <p>Once you have the x and y, you can confirm if these are indeed the missing elements.</p> <p>If it so happens that the confirmation step fails, then we must have the second case:</p> <blockquote> <p>2) Two elements repeated exactly twice and the rest appearing exactly once.</p> </blockquote> <p>Let the two repeated elements be a and b (x and y are the missing ones).</p> <blockquote> <p>Warning: Math ahead.</p> </blockquote> <p>Let <code>S_k = 1^k + 2^k + .. + n^k</code></p> <p>For instance <code>S_1 = n(n+1)/2</code>, <code>S_2 = n(n+1)(2n+1)/6</code> etc.</p> <p>Now we compute <em>seven</em> things:</p> <pre><code>T_1 = Sum of the elements of the array = S_1 + a + b - x - y. T_2 = Sum of the squares = S_2 + a^2 + b^2 - x^2 - y^2 T_3 = Sum of cubes = S_3 + a^3 + b^3 - x^3 - y^3 T_4 = Sum of fourth powers = S_4 + a^4 + b^4 - x^4 - y^4 ... T_7 = Sum of seventh powers = S_7 + a^7 + b^7 - x^7 - y^7 </code></pre> <p>Note, we can use O(1) words (intsead of one) to deal with the overflow issues. (I estimate 8-10 words will be enough).</p> <p>Let <code>Ci = T_i - S_i</code></p> <p>Now assume that a,b,x,y are the roots of the 4th degree polynomial <code>P(z) = z^4 + pz^3 + qz^2 + rz + s</code></p> <p>Now we try to transform the above seven equations into four linear equations in <code>p,q,r,s</code>.</p> <p>For instance, if we do <code>4th Eqn + p * 3rd Eqn + q* 2nd equation + r* 1st equation</code> </p> <p>we get</p> <p><code>C4 + p*C3 + q*C2 + r*C1 = 0</code></p> <p>Similarly we get</p> <pre><code>C5 + p*C4 + q*C3 + r*C2 + s*C1 = 0 C6 + p*C5 + q*C4 + r*C3 + s*C2 = 0 C7 + p*C6 + q*C5 + r*C4 + s*C3 = 0 </code></pre> <p>These are four linear equations in <code>p,q,r,s</code> which can be solved by Linear Algebra techniques like Gaussian Elimination.</p> <p>Note that <code>p,q,r,s</code> will be rationals and so can be computed only with integer arithmetic.</p> <p>Now suppose we are given a solution <code>p,q,r,s</code> to the above set of equations.</p> <p>Consider <code>P(z) = z^4 + pz^3 + qz^2 + rz + s</code>.</p> <p>What the above equations are saying is basically</p> <pre><code>P(a) + P(b) - P(x) - P(y) = 0 aP(a) + bP(b) - xP(x) -yP(y) = 0 a^2 P(a) + b^2 P(b) - x^2 P(x) - y^2 P(y) = 0 a^3 P(a) + b^3 P(b) - x^3 P(x) - y^3 P(y) = 0 </code></pre> <p>Now the matrix</p> <pre><code> 1 1 -1 -1 a b -x -y a^2 b^2 -x^2 -y^2 a^3 b^3 -x^3 -y^3 </code></pre> <p>has the same determinant as the <a href="http://en.wikipedia.org/wiki/Vandermonde_matrix" rel="noreferrer">Vandermonde matrix</a> and thus is invertible, if <code>a,b,x,y</code> are distinct.</p> <p>Thus we must have that <code>P(a) = P(b) = P(x) = P(y) = 0</code>.</p> <p>Now check which of <code>1,2,3,...,n</code> are roots of <code>x^4 + px^3 + qx^2 + rx + s = 0</code>.</p> <p>Thus this is a linear time constant space algorithm.</p> <hr> <p><strong>Code</strong></p> <p>I wrote the following C# (.Net 4.0) code and it seems to work for the few samples I tried... (Note: I didn't bother catering to case 1 above).</p> <pre><code>using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Numerics; namespace SOManaged { class Program { static void Main(string[] args) { ulong[] inp = {1,3,2,1,2}; ulong[] inp1 = { 1,2,3,4,5,6,7,8, 9,10,11,13,14,15, 16,17,18,19,20,21,5,14}; int N = 100000; ulong[] inp2 = new ulong[N]; for (ulong i = 0; i &lt; (ulong)N; i++) { inp2[i] = i+1; } inp2[122] = 44; inp2[419] = 13; FindMissingAndRepeated(inp); FindMissingAndRepeated(inp1); FindMissingAndRepeated(inp2); } static void FindMissingAndRepeated(ulong [] nums) { BigInteger[] C = new BigInteger[8]; // Compute the C_i for (int k = 0; k &lt; 8; k++) { C[k] = 0; } BigInteger i = 1; BigInteger n = 0; for (int j = 0; j &lt; nums.Length; j++) { n = nums[j]; i = j + 1; for (int k = 1; k &lt; 8; k++) { C[k] += i - n; n = n * nums[j]; i = i * (j + 1); } } for (int k = 1; k &lt;= 7; k++) { Console.Write("C[" + k.ToString() + "] = " + C[k].ToString() +", "); } Console.WriteLine(); // Solve for p,q,r,s BigInteger[] pqrs = new BigInteger[4]; BigInteger[] constants = new BigInteger[4]; BigInteger[,] matrix = new BigInteger[4, 4]; int start = 4; for (int row = 0; row &lt; 4; row++ ) { constants[row] = -C[start]; int k = start-1; for (int col = 0; col &lt; 4; col++) { matrix[row, col] = C[k]; k--; } start++; } Solve(pqrs, matrix, constants, 4); for (int k = 0; k &lt; 4; k++) { Console.Write("pqrs[" + k.ToString() + "] = " + pqrs[k].ToString() + ", "); } Console.WriteLine(); // Find the roots. for (int k = 1; k &lt;= nums.Length; k++) { BigInteger x = new BigInteger(k); BigInteger p_k = x * x * x* x + pqrs[0] * x* x * x + pqrs[1] * x * x + pqrs[2] * x + pqrs[3]; if (p_k == 0) { Console.WriteLine("Found: " + k.ToString()); } } } // Solve using Cramer's method. // matrix * pqrs = constants. static void Solve(BigInteger[] pqrs, BigInteger[,] matrix, BigInteger[] constants, int n) { BigInteger determinant = Determinant(matrix, n); for (int i = 0; i &lt; n; i++) { BigInteger[,] numerator = Replace(matrix, constants, n, i); BigInteger numDet = Determinant(numerator,4); pqrs[i] = numDet/ determinant; } } // Replace a column of matrix with constants. static BigInteger[,] Replace(BigInteger[,] matrix, BigInteger[] constants, int n, int col) { BigInteger[,] newMatrix = new BigInteger[n, n]; for (int i = 0; i &lt; n; i++) { for (int j = 0; j &lt; n; j++) { if (j != col) { newMatrix[i, j] = matrix[i, j]; } else { newMatrix[i, j] = constants[i]; } } } return newMatrix; } // Recursively compute determinant for matrix. static BigInteger Determinant(BigInteger[,] matrix, int n) { BigInteger determinant = new BigInteger(0); int multiplier = 1; if (n == 1) { return matrix[0,0]; } for (int i = 0; i &lt; n; i++) { BigInteger [,] subMatrix = new BigInteger[n-1,n-1]; int row = 0; for (int j=1; j &lt; n; j++) { int col = 0; for (int k = 0; k &lt; n ; k++) { if (k == i) { continue; } subMatrix[row,col] = matrix[j,k]; col++; } row++; } BigInteger subDeterminant = Determinant(subMatrix, n - 1); determinant += multiplier * subDeterminant * matrix[0,i]; multiplier = -multiplier; } return determinant; } } } </code></pre> <p>The output is</p> <pre><code>C[1] = 6, C[2] = 36, C[3] = 180, C[4] = 864, C[5] = 4116, C[6] = 19656, C[7] = 9 4380, pqrs[0] = -12, pqrs[1] = 49, pqrs[2] = -78, pqrs[3] = 40, Found: 1 Found: 2 Found: 4 Found: 5 C[1] = 15, C[2] = 407, C[3] = 9507, C[4] = 215951, C[5] = 4861515, C[6] = 108820 727, C[7] = 2424698067, pqrs[0] = -53, pqrs[1] = 980, pqrs[2] = -7396, pqrs[3] = 18480, Found: 5 Found: 12 Found: 14 Found: 22 C[1] = 486, C[2] = 189424, C[3] = 75861486, C[4] = 31342069984, C[5] = 130971109 69326, C[6] = 5492487308851024, C[7] = 2305818940736419566, pqrs[0] = -600, pqrs[1] = 83183, pqrs[2] = -3255216, pqrs[3] = 29549520, Found: 13 Found: 44 Found: 123 Found: 420 </code></pre>
    singulars
    1. This table or related slice is empty.
    1. POFinding missing elements in an array
      singulars
      1. PTQuestion
    1. PTAnswer
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. POFinding missing elements in an array
      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. COIf this works, it's brilliant. :)
      singulars
      1. PO
      1. USGeorg Schölly
    2. CO@Georg: Looks right to me :-P. If it works, Thanks! ;-)
      singulars
      1. PO
      1. This table or related slice is empty.
    3. CO@Georg: Here is some data. For the example problem `1,1,2,2,3`: `c1 = 6 C2 = 36 c3 = 180 C4 = 864 C5 = 4116 C6 = 19656 C7 = 94380` Solving gives `p=-12, q= 49, r = -78, s= 40`. THe corresponding polynomial is `(z-1)(z-2)(z-4)(z-5)`
      singulars
      1. PO
      1. This table or related slice is empty.
 

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