Find a pair of elements from an array whose sum equals a given number

by

There are 3 approaches to this solution:

Let the sum be T and n be the size of array

Approach 1:
The naive way to do this would be to check all combinations (n choose 2). This exhaustive search is O(n2).

Approach 2: 
 A better way would be to sort the array. This takes O(n log n)
Then for each x in array A,
use binary search to look for T-x. This will take O(nlogn).
So, overall search is  O(n log n)

Approach 3 :
The best way
would be to insert every element into a hash table (without sorting). This takes O(n) as constant time insertion.
Then for every x,
we can just look up its complement, T-x, which is O(1).
Overall the run time of this approach is O(n).

You can refer more here.Thanks.

More Related Contents:

  1. complexity in terms of big O
  2. Unique (non-repeating) random numbers in O(1)?
  3. How do I create a URL shortener? [closed]
  4. Simple calculations for working with lat/lon and km distance?
  5. Generate all binary strings of length n with k bits set
  6. Finding a single number in a list [duplicate]
  7. Minimum number of swaps needed to change Array 1 to Array 2?
  8. What algorithm gives suggestions in a spell checker?
  9. What’s a good algorithm to determine if an input is a perfect square? [duplicate]
  10. Bitwise and in place of modulus operator
  11. nᵗʰ ugly number
  12. Optimal algorithm for returning top k values from an array of length N
  13. Find connected components in a graph [closed]
  14. Calculate largest inscribed rectangle in a rotated rectangle
  15. Argument for O(1) average-case complexity of heap insertion
  16. insert, delete, max in O(1)
  17. How Can I Best Guess the Encoding when the BOM (Byte Order Mark) is Missing?
  18. Given two arrays a and b .Find all pairs of elements (a1,b1) such that a1 belongs to Array A and b1 belongs to Array B whose sum a1+b1 = k
  19. How does Dijkstra’s Algorithm and A-Star compare?
  20. Examples of Algorithms which has O(1), O(n log n) and O(log n) complexities
  21. How to cartoon-ify an image programmatically?
  22. Permute all unique enumerations of a vector in R
  23. Is there any fast method of matrix exponentiation?
  24. Easiest algorithm of Voronoi diagram to implement? [closed]
  25. “Rounding” colour values to the nearest of a small set of colours
  26. What algorithm can calculate the power set of a given set?
  27. Color gradient algorithm
  28. Optimized low-accuracy approximation to `rootn(x, n)`
  29. What are probabilistic data structures?
  30. Connected Component Labeling – Implementation

Leave a Comment