Problem of the Day -- Duplicate Numbers

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 :)).

Permalink: http://problemotd.com/problem/duplicate-numbers/

Comments:

Hueho - 10 years, 8 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];
        if(prev_added === elem) continue;
        else if(prev === elem) {
            result.push(elem);
            prev_added = elem;
        }
        prev = elem;
    }
    return result;
}

It will perform under O(n²⁾ as long as the sort is under O(n²⁾ as well.

reply permalink

Carlos - 10 years, 8 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!");
}

reply permalink

Me and myself - 10 years, 8 months ago
Quicksort O(n log n)
and check if the next number is equals :)

reply permalink

Jt - 10 years, 8 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");
      Console.ReadLine();
    }
  }
}

reply permalink

Pufe - 10 years, 8 months ago
bash one-liner: sort input.txt | uniq -d

reply permalink
Jt - 10 years, 8 months ago
Nice

reply permalink

Adam - 10 years, 8 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

reply permalink

Mre64 - 10 years, 6 months ago

/* Mre64 6/13/14

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

*/ import java.util.ArrayList; import java.util.LinkedList;

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
    holdValues.add(1);
    holdValues.add(2);
    holdValues.add(3);
    holdValues.add(4);
    holdValues.add(5);
    holdValues.add(6);
    holdValues.add(5);
    holdValues.add(5);
    holdValues.add(2);
    holdValues.add(10);

    Sort(holdValues);

}
static void Sort(ArrayList<Integer> input){
    // create a copy of the ArrayList with a LinkedList
    LinkedList<Integer> copy = new LinkedList<Integer>();
    // fill copy with origional contents
    for(int i : holdValues){
        copy.add(i);
    }
    /*
       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);
    }
}

}

reply permalink

Mre64 - 10 years, 6 months ago

without comments and a filled data set

import java.util.ArrayList; import java.util.LinkedList;

public class DuplicateNumber { private static ArrayList<Integer> holdValues = new ArrayList<Integer>(); public static void main(String[] args) { Sort(holdValues); } static void Sort(ArrayList<Integer> input){ LinkedList<Integer> copy = new LinkedList<Integer>(); for(int i : holdValues){ copy.add(i); } while(!copy.isEmpty()){ int store = copy.get(0); copy.removeFirst(); if(copy.contains(store)) System.out.println(store); } } }

reply permalink

Problem of the Day A new programming or logic puzzle every Mon-Fri

Duplicate Numbers

Comments:

Problem of the Day
A new programming or logic puzzle every Mon-Fri