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:

In your solution, you should modify the Partition algorithm

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