Quadratic algorithm for 4-SUM

by

Yes you can. Go over all pairs of numbers and store their sum(and also store which numbers give that sum). After that for each sum check if its negation is found among the sums you have. Using a hash you can reach quadratic complexity, using std::map, you will reach O(n^2*log(n)).

EDIT: to make sure no number is used more than once it will better to store indices instead of the actual numbers for each sum. Also as a given sum may be formed by more than one pair, you will have to use a hash multimap. Having in mind the numbers are different for a sum X = a1 + a2 the sum -X may be formed at most once using a1 and once using a2 so for a given sum X you will have to iterate over at most 3 pairs giving -X as sum. This is still constant.

More Related Contents:

  1. Algorithm to find the maximum sum in a sequence of overlapping intervals
  2. Calculate the sum with minimum usage of numbers
  3. Sum a number with divisors to get another number
  4. Priority scoring algorithm [closed]
  5. What is the optimal algorithm for the game 2048?
  6. How to count the number of set bits in a 32-bit integer?
  7. Reverse the ordering of words in a string
  8. Converting a Uniform Distribution to a Normal Distribution
  9. Can hash tables really be O(1)?
  10. Graph Algorithm To Find All Connections Between Two Arbitrary Vertices
  11. What is Sliding Window Algorithm? Examples?
  12. Diff Algorithm? [closed]
  13. Choosing n numbers with fixed sum
  14. Fast way to calculate n! mod m where m is prime?
  15. Store the largest 5000 numbers from a stream of numbers
  16. Sum-subset with a fixed subset size
  17. What is a good Hash Function?
  18. Algorithm for “nice” grid line intervals on a graph
  19. How to calculate the entropy of a file?
  20. Travelling Salesman with multiple salesmen?
  21. Longest acyclic path in a directed unweighted graph
  22. 3 dimensional bin packing algorithms
  23. A Cache Efficient Matrix Transpose Program?
  24. Faster version of find for sorted vectors (MATLAB)
  25. Number of paths between two nodes in a DAG
  26. Word comparison algorithm
  27. Efficient algorithm for finding all maximal subsets
  28. Is it possible to find two numbers whose difference is minimum in O(n) time
  29. Creating combinations that have no more one intersecting element
  30. CUDA stream compaction algorithm

Leave a Comment