# Problem of the DayA new programming or logic puzzle every Mon-Fri

## Duplicate Numbers

Hopefully while filling out your taxes you didn't run in to any issues with duplicate numbers. However, if you did now is your chance to make up for it. For today's problem you'll be passed in an array of integers and asked to identify all the duplicate numbers.

For a bonus solve it in under O(n^2) without making use of a set/hash (unless you want to implement your own :)).

• Hueho - 3 years, 2 months ago

This problem is made easier by the fact that we are dealing with integers, which are ordered.

So we just need to sort the array, and scan it in a single pass to check for repeated elements.

Simple code in JavaScript:

``````function num_cmp(a, b) {
return a - b;
}

function duplicates(arr) {
arr.sort(num_cmp);
var result = [], prev = arr[0], prev_added = null;
for(var i = 1, len = arr.length; i < len; i++){
var elem = arr[i];
else if(prev === elem) {
result.push(elem);
}
prev = elem;
}
return result;
}
``````

It will perform under O(n2) as long as the sort is under O(n2) as well.

• Carlos - 3 years, 2 months ago

The sort is O(n log(n)) according to javadoc, it does show several times if a number is duplicated more than once but, that could easily be saved with a storing array and a simple if, and display the numbers at the end.

``````private static void findDuplicates(int[] array) {
int c = 0;
Arrays.sort(array);
for(int i = 1; i < array.length; i++)
if(array[i] == array[i - 1]) {
System.out.println("Found duplicate, it's: " + array[i]);
c++;        //HAHAHAHAH get it!!, C++... HAHAHAHAHA...
}
if(c == 0) System.out.println("No duplictes were found!");
}
``````
• Me and myself - 3 years, 2 months ago

Quicksort O(n log n)
and check if the next number is equals :)

• Jt - 3 years, 2 months ago

C#, not sure what O it is. I did a small amount of reading and there seems to be some complexities to how Linq handles it under the scenes. I will have to do some more research later.

``````namespace ProblemOtd20140416
{
using System;
using System.Linq;

class Program
{
static void Main(string[] args)
{
Random random = new Random();
int[] intArray = new int[100];

// Give me 100 numbers between 0 and 50. Some will be duplicated, hopefully not all of them. :)
for (int index = 0; index < 100; index++)
{
intArray[index] = random.Next(50);
}

// Give me a distinct list of numbers that occur in the array more then once
foreach (int index in intArray.Where(index => intArray.Count(checkInt => checkInt == index) > 1).Distinct())
{
Console.WriteLine(index + " is duplicated");
}

Console.WriteLine("Finished press enter to exit");
}
}
}
``````
• Pufe - 3 years, 2 months ago

bash one-liner: `sort input.txt | uniq -d`

• Jt - 3 years, 2 months ago

Nice

• Adam - 3 years, 2 months ago

This is quite nice in Haskell:

``````duplicates :: Ord a => [a] -> [a]
duplicates = removeRepeats . map fst . filter (\(a, b) -> a == b) . pairs . sort

pairs :: [a] -> [(a, a)]
pairs (x:y:rest) = (x, y) : pairs (y:rest)
pairs _ = []

removeRepeats :: Eq a => [a] -> [a]
removeRepeats (x:y:rest) | x == y    = removeRepeats (y : rest)
removeRepeats (x:y:rest) | otherwise = x : removeRepeats (y : rest)
removeRepeats xs = xs
``````
• - 3 years ago

/* Mre64 6/13/14

``````«The doctors X-rayed my head and found nothing.»
- Dizzy Dean, baseball player 1934 world series
``````

public class DuplicateNumber { //create an ArrayList which holds the values to be tested for duplicates private static ArrayList<Integer> holdValues = new ArrayList<Integer>();

``````public static void main(String[] args) {
// TODO Auto-generated method stub

Sort(holdValues);

}
static void Sort(ArrayList<Integer> input){
// create a copy of the ArrayList with a LinkedList
// fill copy with origional contents
for(int i : holdValues){
}
/*
we will be checking if copies exist by copying
the first element of the copy LinkedList, erasing
the first element, and checking the list against that.
*/
//ensure List is not empty while checking
while(!copy.isEmpty()){
//copy value of first element
int store = copy.get(0);
//remove first element
copy.removeFirst();
//check against store
if(copy.contains(store))
System.out.println(store);
}
}
``````

}

• - 3 years ago

without comments and a filled data set