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

Comments:

• Hueho - 10 years 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 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 ago

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

  reply permalink

• Jt - 10 years 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 ago

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

  reply permalink

• Jt - 10 years ago

  Nice

  reply permalink

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