Cyclic Sort

Question 1

Find the Missing Number

We are given an array containing ‘n’ distinct numbers taken from the range 0 to ‘n’. Since the array has only ‘n’ numbers out of the total ‘n+1’ numbers, find the missing number.

Example 1:
Input: [4, 0, 3, 1]
Output: 2

TC – O(n)
SC – O(1)

Answer 1

Input: [4, 0, 3, 1]
Output: 2

Pseudo code:

1. Sort the array with below steps.
   a. Iterate the array one number at a time.
   b. Place ‘1’ at index ‘1’, place ‘2’ at index ‘2’
   c. If number is not at correct index, swap it with the number at its correct index and don’t increase the index else increase the index.
2. This way we will go through all numbers and place them in their correct indices
3. Iterate one more time and if index and value is not same, return index.

Takeaway: Take the while loop where index less than array length