-
-
Save vagetablechicken/31b210446ec55944cb490c658c3c6a04 to your computer and use it in GitHub Desktop.
grokking5-pc1
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
''' | |
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() |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment