Implement an oracle/oracle.cpp file that can be told a sequence of numbers containing every number from 1 to 1000000, except for one or two, and returns the missing number(s).2 If this seems impossible, just consider the following facts:

Theorem 1.1. Let x1, x2, . . . , xn1, y be a permutation of the numbers from 1 to n. Then y = n(n+1) 2 Pn1 i=1 xi.

Theorem 1.2. Let x1, x2, . . . , xn2, y1, y2 be a permutation of the numbers from 1 to n. Let s = y1 +y2 and t = y 2 1+y 2 2 . Then s = n(n+1)/2 Pn2 i=1 xi and t = n(n+1)(2n+1) 6 Pn2 i=1 x 2 i . Moreover, 2y 2 12sy1+s 2t = 0.

Theorem 1.3 (Quadratic formula). Let a, b, c, x R with ax2 + bx + c = 0. Then x = b b 24ac 2a.

Only include these libraries.

#include #include #include #include #include

#include "oracle.h"

based off this oracle.h

#ifndef ORACLE_H

#define ORACLE_H

#include

class Oracle

{

public:

// Creates a new oracle, ready to be told all numbers

// (in any order) from 1 to 1000000, except for one or two.

//

// Must run in O(1) time.

Oracle();

// Tells the oracle a number between 1 and 1000000 not yet told.

//

// Must run in O(1) time.

void tell(int i);

// If every number between 1 and 1000000 except one have

// been told, and no number has been told more than once,

// sets x equal to the one number not yet told.

//

// Otherwise has undefined behavior.

//

// Must run in O(1) time.

void missing_one(int &x);

// If every number between 1 and 1000000 except two have

// been told, and no number has been told more than once,

// sets x and y equal to the two numbers not yet told (where x < y).

//

// Otherwise has undefined behavior.

//

// Must run in O(1) time.

void missing_two(int &x, int &y);

private:

long long int data[2];

};

#endif