grokking5-pc1

FindtheCorruptPair

'''
Problem Challenge 1

Find the Corrupt Pair (easy)

We are given an unsorted array containing ‘n’ numbers taken from the range 1 to ‘n’. The array originally contained all the numbers from 1 to ‘n’, but due to a data error, one of the numbers got duplicated which also resulted in one number going missing. Find both these numbers.

Example 1:

Input: [3, 1, 2, 5, 2]
Output: [2, 4]
Explanation: '2' is duplicated and '4' is missing.

Example 2:

Input: [3, 1, 2, 3, 6, 4]
Output: [3, 5]
Explanation: '3' is duplicated and '5' is missing.
'''
def find_corrupt_numbers_v1(nums):
    i = 0
    while i < len(nums):
        if nums[i] > 0 and nums[i] != i + 1:
            v = nums[i]
            if nums[v - 1] == v:
                nums[i], nums[v - 1] = 0, -2
            elif nums[v - 1] == 0:
                nums[i], nums[v - 1] = 0, v
            else:
                nums[i], nums[v - 1] = nums[v - 1], nums[i]
        else:
            i += 1
    result = [-1, -1]
    for i in range(len(nums)):
        if nums[i] == -2:
            result[0] = i + 1
        elif nums[i] == 0:
            result[1] = i + 1
    return result

def find_corrupt_numbers(nums):
    i = 0
    while i < len(nums):
        j = nums[i] - 1
        if nums[i]!=nums[j]:
            nums[i], nums[j] = nums[j], nums[i]
        else:
            i+=1
    for i in range(len(nums)):
        if nums[i]!=i+1:
            return [nums[i], i+1]
    return [-1,-1]

def main():
    print(find_corrupt_numbers([3, 1, 2, 5, 2]))
    print(find_corrupt_numbers([3, 1, 2, 3, 6, 4]))


main()