About usWhy usInstructorsReviewsCostFAQContactBlogRegister for Webinar

Duplicate in a Loose Permutation Problem

Find a duplicated number in a loose permutation of numbers. A permutation is an array that is size n, and also has positive numbers from 1 to n. A loose permutation is a permutation where some numbers are missing and some are duplicated, but the total number is still n.


Example One

Input: [1, 2, 7, 3, 4, 4, 5]

Output: 4

We can see that 4 is a duplicate number here as it is present 2 times in the array.


Example Two

Input: [1, 2, 3]

Output: -1

There is no duplicate number present, so we return -1.


Notes

Input Parameters: The function has one argument, an integer array.

Output: Return an integer, any one of the duplicate numbers present in the array. If no duplicate number is present, return -1.


Constraints:

● 1

● 1

● Input array may or may not be sorted.

● You can only use a constant extra memory.


Solution

We provided one solution.

● We are given an input array of integers. 

● We start iterating over this array and for every integer encountered, say we encounter integer 5, we negate the value at index (abs(integer) -1), here (abs(5)-1 = 4), in the input array.

● So if the array was [5, 1, 2, 3, 3], after iterating through the first element, that is 5, it would become [5, 1, 2, 3, -3].

● Note that we are using abs(integer) because over the subsequent iterations, we may start getting negative numbers at certain array positions, hence we use the absolute values of array integers.

● Now, if we try to negate a number at a certain position, which is already negated, we can be certain that this number is a duplicate because that position which corresponds to the number has already been negated.

● If the number was a unique one, then it would not had that position negated. 

● To illustrate let's come back to our array [5, 1, 2, 3, 3], after iterating through the first 4 elements and updating the array as we discussed, we get the following array [-5, -1, -2, 3, -3]. 

● Now when we encounter the last element, that is -3, we try to negate the value at index (abs(-3)-1), which is value at index 2, and that is already negated. So we identify 3 as a duplicate.


Time Complexity:

O(n). We iterate all the elements of the array only once.

Auxiliary Space Used:

O(1).

Space Complexity:

O(n) due to the size of input.