C++: Find Duplicates in a Positive Integers Range 1 to N

Given an array of integers where each value 1 <= x <= len(array), write a function that finds all the duplicates in the array.

C++ Solution

#include<iostream>
#include <vector>
using namespace std;
vector<int> findDuplicates(int arr[], int len) {
vector<int> result;
for(int i = 0; i < len; i++) {
int index = abs(arr[i]) - 1;
if (arr[index] < 0) {
result.push_back(arr[i]);
} else {
arr[index] = -arr[index];
}
}
return result;
}
int main() {
vector<int> v;
int arr[5] = {1,2,2,3,1};
v = findDuplicates(arr, 5);
for (auto i = v.begin(); i != v.end(); i++) {
cout << *i << " ";
}
cout << endl;
return 0;
}
$ g++ -std=c++11 ./FindDuplicates.cc
$ ./a.out
1 2

Reference

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.

%d bloggers like this: