Algorithm to find two repeated numbers in an array, without sorting

by

There is a O(n) solution if you know what the possible domain of input is. For example if your input array contains numbers between 0 to 100, consider the following code. 

bool flags[100];
for(int i = 0; i < 100; i++)
    flags[i] = false;

for(int i = 0; i < input_size; i++)
    if(flags[input_array[i]])
         return input_array[i];
    else       
        flags[input_array[i]] = true;

Of course there is the additional memory but this is the fastest.

More Related Contents:

  1. What should be the algorithm of the below statement?
  2. Finding all possible combinations of numbers to reach a given sum
  3. How do I search for a number in a 2d array sorted left to right and top to bottom?
  4. Generate an integer that is not among four billion given ones
  5. Nearest neighbors in high-dimensional data?
  6. Backtracking in A star
  7. how to calculate binary search complexity
  8. Binary Search in Array
  9. Algorithm to find multiple string matches
  10. Fast Algorithm to Quickly Find the Range a Number Belongs to in a Set of Ranges?
  11. O(klogk) time algorithm to find kth smallest element from a binary heap
  12. Print the biggest K elements in a given heap in O(K*log(K))?
  13. Find local minimum in n x n matrix in O(n) time
  14. Breadth First Search and Depth First Search
  15. What is the difference between Linear search and Binary search?
  16. How to count the number of set bits in a 32-bit integer?
  17. Algorithm to return all combinations of k elements from n
  18. Graph Algorithm To Find All Connections Between Two Arbitrary Vertices
  19. Algorithm to randomly generate an aesthetically-pleasing color palette [closed]
  20. Algorithm to tell if two arrays have identical members
  21. Quicksort vs heapsort
  22. Find 2 numbers in an unsorted array equal to a given sum
  23. Simplest way to get the top n elements of a Scala Iterable
  24. Find cycle of shortest length in a directed graph with positive weights
  25. How is 2D bin packing achieved programmatically?
  26. What is the best way to check the strength of a password?
  27. Algorithm for merging two max heaps?
  28. What is the algorithm that opencv uses for finding contours?
  29. Find XOR of all numbers in a given range
  30. Best algorithm for matching colours.

Leave a Comment