Register for our webinar

### How to Nail your next Technical Interview

1 hour
1
Enter details
2
Select webinar slot
*Invalid Name
*Invalid Name
Step 1
Step 2
Congratulations!
You have registered for our webinar
Oops! Something went wrong while submitting the form.
1
Enter details
2
Select webinar slot
*All webinar slots are in the Asia/Kolkata timezone
Step 1
Step 2
Confirmed
You are scheduled with Interview Kickstart.
Redirecting...
Oops! Something went wrong while submitting the form.

## You may be missing out on a 66.5% salary hike*

### Nick Camilleri

Head of Career Skills Development & Coaching
*Based on past data of successful IK students
Help us know you better!

## How many years of coding experience do you have?

Oops! Something went wrong while submitting the form.

## FREE course on 'Sorting Algorithms' by Omkar Deshpande (Stanford PhD, Head of Curriculum, IK)

Oops! Something went wrong while submitting the form.

# Duplicate In A Loose Permutation Problem Statement

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

``````{
"arr": [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

``````{
"arr": [1, 2, 3]
}
``````

Output:

``````-1
``````

## Notes

• You can only use a constant amount of extra memory.
• If no duplicate number is present, return -1.
• If multiple duplicates exist, return any.

Constraints:

• 1 <= `n` <= 106
• 1 <= any element of the input list <= `n`

We provided one solution.

Throughout this editorial, we will refer to the length of the input array as `n`.

# Duplicate In A Loose Permutation Solution: Optimal

• 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.

O(1).

## Space Complexity

O(n).

Space used for input: O(n).

Auxiliary space used: O(1).

Space used for output: O(1).

So, total space complexity: O(n).

## Code For Duplicate In A Loose Permutation Solution: Optimal

``````/*
Asymptotic complexity in terms of the length of the input array \`n\`:
* Time: O(n).
* Auxiliary space: O(1).
* Total space: O(n).
*/

int find_duplicate(vector<int> &arr) {
for (int i = 0; i < arr.size(); i++) {
int value = abs(arr[i]) - 1;
if (arr[value] < 0) {
return abs(arr[i]);
}
else {
arr[value] = -arr[value];
}
}
// If no duplicate is present, we return -1.
return -1;
}
``````

We hope that these solutions to finding duplicate in a loose permutation problem have helped you level up your coding skills. You can expect problems like these at top tech companies like Amazon and Google.

If you are preparing for a tech interview at FAANG or any other Tier-1 tech company, register for Interview Kickstart’s FREE webinar to understand the best way to prepare.

Interview Kickstart offers interview preparation courses taught by FAANG+ tech leads and seasoned hiring managers. Our programs include a comprehensive curriculum, unmatched teaching methods, and career coaching to help you nail your next tech interview.

We offer 18 interview preparation courses, each tailored to a specific engineering domain or role, including the most in-demand and highest-paying domains and roles, such as:

### Try yourself in the Editor

Note: Input and Output will already be taken care of.

# Duplicate In A Loose Permutation Problem Statement

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

``````{
"arr": [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

``````{
"arr": [1, 2, 3]
}
``````

Output:

``````-1
``````

## Notes

• You can only use a constant amount of extra memory.
• If no duplicate number is present, return -1.
• If multiple duplicates exist, return any.

Constraints:

• 1 <= `n` <= 106
• 1 <= any element of the input list <= `n`

We provided one solution.

Throughout this editorial, we will refer to the length of the input array as `n`.

# Duplicate In A Loose Permutation Solution: Optimal

• 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.

O(1).

## Space Complexity

O(n).

Space used for input: O(n).

Auxiliary space used: O(1).

Space used for output: O(1).

So, total space complexity: O(n).

## Code For Duplicate In A Loose Permutation Solution: Optimal

``````/*
Asymptotic complexity in terms of the length of the input array \`n\`:
* Time: O(n).
* Auxiliary space: O(1).
* Total space: O(n).
*/

int find_duplicate(vector<int> &arr) {
for (int i = 0; i < arr.size(); i++) {
int value = abs(arr[i]) - 1;
if (arr[value] < 0) {
return abs(arr[i]);
}
else {
arr[value] = -arr[value];
}
}
// If no duplicate is present, we return -1.
return -1;
}
``````

We hope that these solutions to finding duplicate in a loose permutation problem have helped you level up your coding skills. You can expect problems like these at top tech companies like Amazon and Google.

If you are preparing for a tech interview at FAANG or any other Tier-1 tech company, register for Interview Kickstart’s FREE webinar to understand the best way to prepare.

Interview Kickstart offers interview preparation courses taught by FAANG+ tech leads and seasoned hiring managers. Our programs include a comprehensive curriculum, unmatched teaching methods, and career coaching to help you nail your next tech interview.

We offer 18 interview preparation courses, each tailored to a specific engineering domain or role, including the most in-demand and highest-paying domains and roles, such as: