Find the Corrupt Pair

Try to solve the Find the Corrupt Pair problem.

We'll cover the following

Statement#

We are given an unsorted array, nums, with nn elements and each element is in the range [1,n][1, n] inclusive. The array originally contained all the elements from 11 to nn but due to a data error, one of the numbers is duplicated, which causes another number missing. Find and return the corrupt pair (missing, duplicated).

Constraints:

  • 2≤n≤1032 \leq n \leq 10^3
  • 1≤1 \leq nums[i] ≤n\leq n

Examples#

Created with Fabric.js 3.6.6 Input 5 1 Array 4 1 2 1 6 3 Sample example 1

1 of 3

Created with Fabric.js 3.6.6 4 2 Input Array 3 1 2 5 2 Sample example 2

2 of 3

Created with Fabric.js 3.6.6 4 1 Input Array 7 1 2 3 1 5 6 Sample example 3

3 of 3

Understand the problem#

Let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

Find the Corrupt Pair

1

Which is the corrupt pair in the array given below?

[4, 1, 3, 4, 5]

A)

2, 3

B)

2, 4

C)

2, 5

D)

2, 6

Question 1 of 30 attempted

Figure it out!#

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Drag and drop the cards to rearrange them in the correct sequence.

Apply the cyclic sort to the array.

After sorting, traverse the array and find the number that isn’t at its correct position. This will be the duplicate number.

Add 11 to the index of the duplicate number. This will be our missing number.

Return the pair containing the missing and duplicated number.

Try it yourself#

Implement your solution in the following coding playground:

Python
usercode > main.py
Input #1
%0 node_01 3 node_11 1 node_21 2 node_31 5 node_41 2
Visualization for Input #1
Find the Corrupt Pair

Solution: Missing Number

Solution: Find the Corrupt Pair