We have an unsorted array size of n-1, that has the numbers from 1 to n excluding one number. We need to find that missing number.

Like if we have as input [8,1,5,4,2,7,6], then it should return 3.

Constraints I got:

Try to collect smaller patient numbers to the left and bigger numbers to the right. In your solution, you have to use the Partition algorithm that is used by QuickSort (solutions that do not use partitioning and recursion, such as subtracting the sum of the elements in A from the sum of the integers up-to n will not be a valid answer).

How is this possible?

CodePudding user response：

This problem can be solved with an algorithm that is much like quickselect:

The idea is to partition the input array like with quickselect (and quicksort). At that point we know the pivot element appears where it would be when the array would have been sorted. There are two possibilities:

• The value of the pivot is 2 more than the index where it resides. For instance if we have [1, 3, 4] and the middle element is the pivot, then indeed the value 3 is two more than the index (1) where it resides.

  In this case we can conclude that the missing value is less than the pivot value, and we could repeat the process recursively in the left partition

• The value of the pivot is 1 more than the index where it resides. For instance if we have [1, 2, 4] and the middle element is the pivot, then indeed the value 2 is one more than the index (1) where it resides.

  In this case we can conclude that the missing value is greater than the pivot value, and we could repeat the process recursively in the right partition

Here is an implementation of that algorithm in Python code:

from random import randint

def partition(arr, l, r):
    i = randint(l, r)  # choose pivot randomly
    arr[i], arr[r] = arr[r], arr[i]  # swap it out of the way
    x = arr[r]  # get pivot value
    i = l
    for j in range(l, r):
        if arr[j] <= x:
            arr[i], arr[j] = arr[j], arr[i]  # swap
            i  = 1
    # swap pivot element into its final place
    arr[i], arr[r] = arr[r], arr[i]
    return i
  
def findmissing(arr, l, r):
    if l > r:  # base case
        return arr[r]   1 if r >= 0 else 1
    pivotindex = partition(arr, l, r)
    if arr[pivotindex] == pivotindex   2:  # missing element must be on the left
        return findmissing(arr, l, pivotindex - 1)
    else:  # missing element is on the right
        return findmissing(arr, pivotindex   1, r)

# Demo run
arr = [8,1,5,4,2,7,6]
print(findmissing(arr, 0, len(arr)-1))   # 3