Problem of the Day
A 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 :)).

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

Comments:

  • Hueho - 3 years, 4 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(n2) as long as the sort is under O(n2) as well.

    reply permalink

  • Carlos - 3 years, 4 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 - 3 years, 4 months ago

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

    reply permalink

  • Jt - 3 years, 4 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 - 3 years, 4 months ago

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

    reply permalink

  • Jt - 3 years, 4 months ago

    Nice

    reply permalink

  • Adam - 3 years, 4 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 - 3 years, 2 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 - 3 years, 2 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

Content curated by @MaxBurstein