Linear time algorithm for 2-SUM

by

This is type of Subset sum problem

Here is my solution. I don’t know if it was known earlier or not. Imagine 3D plot of function of two variables i and j: 

sum(i,j) = a[i]+a[j]

For every i there is such j that a[i]+a[j] is closest to x. All these (i,j) pairs form closest-to-x line. We just need to walk along this line and look for a[i]+a[j] == x:

 int i = 0; 
 int j = lower_bound(a.begin(), a.end(), x)  -  a.begin(); 
 while (j >= 0 && j < a.size()  &&  i < a.size())  {  
    int sum = a[i]+a[j]; 
    if (sum == x)   { 
        cout << "found: " << i << " " << j << endl;  
        return;
    }
    if (sum > x)    j--;
    else            i++;
    if (i > j) break;
 }  
 cout << " not found\n";

Complexity: O(n)

More Related Contents:

  1. Unique (non-repeating) random numbers in O(1)?
  2. Find a pair of elements from an array whose sum equals a given number
  3. Algorithm for Additive Color Mixing for RGB Values
  4. The Most Efficient Way To Find Top K Frequent Words In A Big Word Sequence
  5. Fast permutation -> number -> permutation mapping algorithms
  6. Algorithm to detect intersection of two rectangles?
  7. An efficient compression algorithm for short text strings [closed]
  8. How do you calculate the average of a set of circular data? [closed]
  9. circle-circle collision
  10. Generating the partitions of a number
  11. Finding maximum for every window of size k in an array
  12. Generate all unique substrings for given string
  13. Non-recursive depth first search algorithm [closed]
  14. How to detect the BPM of a song in php [closed]
  15. How do you validate a binary search tree?
  16. Floating Point Divider Hardware Implementation Details
  17. Best algorithm to test if a linked list has a cycle
  18. nᵗʰ ugly number
  19. How to partition an array of integers in a way that minimizes the maximum of the sum of each partition?
  20. How to rank a million images with a crowdsourced sort
  21. Why use Dijkstra’s Algorithm if Breadth First Search (BFS) can do the same thing faster?
  22. “Rounding” colour values to the nearest of a small set of colours
  23. What algorithm can calculate the power set of a given set?
  24. Color gradient algorithm
  25. Which is faster, Hash lookup or Binary search?
  26. Finding groups of similar strings in a large set of strings
  27. Tournament bracket placement algorithm
  28. Why is bubble sort O(n^2)?
  29. Location of highest density on a sphere
  30. Why is the “start small” algorithm for branch displacement not optimal?

Leave a Comment