Consider the LARGESTMISSINGNUMBER problem below. Note that in this problem, ther

Question

Consider the LARGESTMISSINGNUMBER problem below. Note that in this problem, there are two parameters n and k that dictate the constraints on the input instead of just the array size n. Input: An array A of n integers in the range [1, k]. Output The largest value x elementof {1, 2, 3 ..., k} which is not contained in A, or -1 if no such value exists. For example, with n = 10, k = 6 and A = [4, 3, 6, 4, 4, 1, 3, 6, 4, 1], the result is 5. (a) Give pseudocode for a O(n + k) algorithm which solves LARGESTMISSINGNUMBER. Briefly justify why the algorithm works. (b) In cases where k is very large (e.g. if k greaterthanorequalto n^2), the algorithm from part (a) would not be linear in the input size. Give pseudocode for a O(n log_2 n) algorithm which solves LARGESTMISSINGNUMBER (where the running time is not influenced by the choice value of k). (c) Briefly describe why any algorithm for LARGESTMISSINGNUMBER must be Ohm(n) in the worst case.

Explanation / Answer

#include <stdio.h>

void swap(int *xp, int *yp)
{
int temp = *xp;
*xp = *yp;
*yp = temp;
}

// A function to implement bubble sort
void bubbleSort(int arr[], int n)
{
int i, j;
for (i = 0; i < n-1; i++)

// Last i elements are already in place   
for (j = 0; j < n-i-1; j++)
if (arr[j] > arr[j+1])
swap(&arr[j], &arr[j+1]);
}

/* Function to print an array */
void printArray(int arr[], int size)
{
int i;
for (i=0; i < size; i++)
printf("%d ", arr[i]);
printf(" ");
}

int main(void) {
   int i, n, k;
   scanf("%d %d", &n, &k);
   int arr[n];
   for(i=0; i<n; i++)
   scanf("%d", &arr[i]);
   bubbleSort(arr, n);
int temp=k+1;
for(i=n-1; i>=0; i--)
{
if(i!=n-1 && arr[i]==arr[i+1])
continue;
else
{
temp--;
if(arr[i]!=temp)
{
printf("%d ", temp);
break;
}
}
}
   return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

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