For problems where either pseudo-code or C++ code is required, you may simply in

Question

For problems where either pseudo-code or C++ code is required, you may simply include the algorithm written as pseudo-code without being tested as long as the logic is clear and can be easily understood by the grader

Given an array A of size N-1 that contains all integers in the range of 1 to N, except one missing integer, write the pseudo-code or C++ code to implement an efficient linear algorithm (that is, the time complexity is O(N) ) to find the missing number. There are no duplicates in the list. Also, you may not create another array to solve this problem

Explanation / Answer

void findMissing(int array[], int size)

{

int sum;

sum = (size+1)*(size+2)/2;   

for(int i = 0; i< size; i++)

sum = sum - array[i];

cout << sum << endl;

}

//If array[] = {1,2,3,4,6}, size = 5

//sum = (6*7)/2 = 21

//21-1-2-3-4-6 = 5

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.