We have an array $T[N]$ containing all integers in the interval $0 \cdots N$, except one integer.

We want to determine which integer is missing from $T$ using multiple approaches. 

Example: for the following array $T$ of size $N=6$, the missing value is 4.

\begin{array}{|c|c|c|c|c|c|}\hline 5 & 6 & 3 & 2 & 1 & 0 \\\hline \end{array}

1. Write the function \(\texttt{int find(int T[], int N, int e)}\) that given an array $T$ of size $N$ and an integer $e$ returns 1 if $e$ is an element of $T$, otherwise returns 0.
2. Version 1: Loop over the interval $0 \cdots N$ and search for each value in $T$ using the function \(\texttt{find}\), return the missing value. Write the function \(\texttt{int findMissingValueV1(int T[], int N)}\) that given an array $T$ of size $N$ returns the missing value.
3. Write the function \(\texttt{int sumArray(int T[], int N)}\) that given an array $T$ of size $N$ returns the sum of the elements in the array.
4. Version 2: The sum of numbers from 0 to $N$ is equal to $\sum_{i=0}^{N}i=\frac{N\times(N+1)}{2}$. It suffices to calculate the difference between the above sum and the sum of elements in $T$. Using the function \(\texttt{sumArray}\), write the function \(\texttt{int findMissingValueV2(int T[], int N)}\) that given an array $T$ of size $N$ returns the missing value.
5. Version 3: We are trying simultaneously to determine the missing value and to sort the array using minimum selection algorithm. At each iteration, after looking for the minimum on the right side of the array, the first time when the minimum doesn't match the index is the missing value.
   Write the function \(\texttt{int findMissingValueV3(int T[], int N)}\) that given an array $T$ of size $N$ sorts $T$ using minimum selection algorithm, determines and returns the missing value.
6. Bubble sort is a sorting algorithm that repeatedly steps through the array, compares adjacent elements and swaps them if they are in the wrong order. The pass through the array is repeated until the array is sorted. The algorithm is named for the way larger elements bubble to the end of the array.
   Write the function \(\texttt{void bubbleSort(int T[], int N)}\) that sorts array $T$ using bubble sort algorithm.
7. Version 4: We will be using a solution based on binary search. For this, call the function \(\texttt{bubbleSort}\) first to sort $T$. Then modify binary search algorithm to locate the missing value.
   If the middle element matches the index, it means the missing value is on the right side. If the middle element is greater than the index, look on the left side. When there's just one element left to compare, it means you have located the element that precedes the missing value.
   Write the function \(\texttt{int findMissingValueV4(int T[], int N)}\) that given an array $T$ of size $N$ sorts $T$ by calling \(\texttt{bubbleSort}\) function and then finds the missing value using the modified version of binary search algorithm.

int find(int T[], int N, int e)
{
    int i;
    for(i=0;i<N;i++)
        if(T[i]==e)
            return 1;
    return 0;
}

int findMissingValueV1(int T[], int N)
{
	int i;
	for(i=0;i<=N;i++)
	    if(find(T,N,i)==0)
	        return i;
}


int sumArray(int T[], int N)
{
	int i, sum = 0;
	for (i = 0; i<N; i++)
		sum += T[i];
	return sum;
}


int findMissingValueV2(int T[], int N)
{
	return N*(N + 1) / 2 - sumArray(T, N);
}


int findMissingValueV3(int T[], int N)
{
	int i, j, imin, aux, missingvalue=-1;
	for (i = 0; i<N - 1; i++)
	{
		imin = i;
		for (j = i + 1; j<N; j++)
			if (T[j]<T[imin])
				imin = j;
		if (imin != i)
		{
			aux = T[imin];
			T[imin] = T[i];
			T[i] = aux;
		}
		if (missingvalue==-1 && T[i] != i)
			missingvalue = i;
	}
	if (missingvalue == -1)
		return N;
	return missingvalue;
}


void bubblesort(int T[], int N)
{
	int i, j, aux, swapped;
	for (i = N - 1; i>0; i--)
	{
		swapped = 0;
		for (j = 0; j<i; j++)
		{
			if (T[j]>T[j + 1])
			{
				aux = T[j];
				T[j] = T[j + 1];
				T[j + 1] = aux;
				swapped = 1;
			}
		}
		if (!swapped) break;
	}
}


int findMissingValueV4(int T[], int N)
{
	int left, right, middle;
	bubblesort(T, N);
	left = 0;
	right = N - 1;
	while (left<right)
	{
		middle = (left + right) / 2;
		if (T[middle] == middle) left = middle + 1;
		if (T[middle]>middle) right = middle - 1;
	}
	return right + 1;
}