A machine takes in numbers (in any order) from 1 to 1000000 and our functions ba
ID: 3751893 • Letter: A
Question
A machine takes in numbers (in any order) from 1 to 1000000 and our functions based on these theorems looks for that one or two missing numbers. Anyway a friend and I were able to accomplish this but are code is still too similiar. Plus I would like to see any different approaches that might work or be more efficient, thank you. Code Below:
/*************************************************************/
// Must run in O(1) time.
Machine::Machine()
{
data[0] = 0;
data[1] = 0;
}
/*************************************************************/
// Must run in O(1) time.
void Machine::store(int i)
{
data[0] += i;
data[1] += static_cast<long long int>(i)*i;
}
/*************************************************************/
// Must run in O(1) time.
void Machine::one_missed(int &x)
{
//Theorem 1.1. Let x1,x2,...,xn1,y be a permutation of the numbers from 1 to n. Then y = n(n+1)/2
// - E n-1, i=x (Xi)
long long int n = 1000000;
long long int s = (n*(n+1))/2;
x = static_cast<int>(s - data[0]);
}
/*************************************************************/
// Must run in O(1) time.
void Machine::two_missed(int &x, int &y)
{
long long int n = 1000000;
long long int s = ((n*(n+1))/2) - data[0];
long long int t = ((n*(n+1)*(2*n+1))/6) - data[1];
long long int a = 2;
long long int b = -2*s;
long long int c = (s*s) - t;
long long int D = (b*b) - (4*a*c); //discriminant
y = ((-b)+sqrt(D))/(2*a);
x = ((-b)-sqrt(D))/(2*a);
}
Theorem 1.1. Let ri,x2, . .. rn-1y be a permutation of the numbers from 1 to n. Then y (n+1 Theorem 1.2. Let xi,r2,. ..,xn-2.1.2 be a permutation of the numbers from 1 to n. Let sy y2 and ye+. Then s = n(n+ 1)/2-en-2 ri and t-n(n+1 62n +1 )-1-1 r2 . Moreover, 2y_2sn + s2-t = 0. Theorem 1.3 (Quadratic formula). Let a, bc, R with rb0. ThenExplanation / Answer
First of all, It is a very good attempt.
Hats off to you and your friend.
The above written functions by you are efficient to implement,
submit it as your homework.