Find two elements in an array that sum to k
Solution 1
There are k pairs of integers that sum to k: {0,k}, {1,k-1}, ... etc. Create an array B of size k+1 where elements are boolean. For each element e of the array A, if e <= k && B[e] == false, set B[e] = true and if B[k-e] == true, emit the pair {e,k-e}. Needs to be extended slightly for negative integers.
Solution 2
One can reduce the,
Element Uniqueness bit,
to this. No O(n).
Solution 3
Just a simple algorithm off the top of my head:
- Create a bitfield that represents the numbers from 0 to k, labeled B
- For each number i in A
- Set B[i]
- If B[k-i] is set, add (i, k-i) to the output
Now as people have raised, if you need to have two instances of the number 3 to output (3, 3) then you just switch the order of the last two statements in the above algorithm.
Also I'm sure that there's a name for this algorithm, or at least some better one, so if anyone knows I'd be appreciative of a comment.
Solution 4
This will print all pairs. The algorithm is same as told by @bdares above.
I have used stl maps as we dont have hash tables in STL.
Related videos on Youtube
Debanjan Chanda
Updated on June 04, 2022Comments
-
Debanjan Chanda almost 2 years
Possible Duplicate:
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 .Given : An unsorted array
A
of integers
Input : An integerk
Output : All the two element set with sum of elements in each set equal to
k
in O(n).Example:
A = {3,4,5,1,4,2}
Input : 6
Output :{3,3}, {5,1}, {4,2}
Note : I know an O(n logn) solution but that would require to have the array sorted. Is there any way by which this problem can be solved in O(n). An non-trivial C++ data structure can be used i.e there's no bound on space
-
Sanjeevakumar Hiremath about 13 yearshow did you derive output pair
{3,3}
? there is only one 3 in input array.
-
-
Admin about 13 yearsYour algorithm takes time O(k*n), where k is the target number. This is much, much worse than O(n).
-
matth about 13 years
std::map<>::insert(x)
is O(log N), andstd::map<>::count(x)
is O(N). Isn't your algorithm thus O(N^2)? -
Vink about 13 years@Rob Adams, I guess, count in map is O(logN) as it does not hold multiple elements with same key. Count in multimap is O(N). My algorithm above is O(NlogN). If we use a hashmap instead of map, we would have O(N) algorithm.
-
Dominik Grabiec about 13 yearsNo, it's O(n), where n is determined by the length of A. The bitfield is a constant time lookup O(1) not a linear time lookup O(n) which you are thinking.
-
Admin about 13 yearsYes, you're right. I misread your algorithm, and assumed you were reading every slot in B.
-
Chiffa over 10 yearsAs of C++11, we kind of do: unordered_map
-
Timofey over 10 yearswhy not to post the code here ;-)
-
Timofey over 10 yearsThis algo needs O(k) space and equivalent to the proposed (java) hashset solutions (in c++ set is a tree)
-
Dominik Grabiec over 10 yearsI think you might be confused Tim, I don't use a set data structure. I use a k sized bitfield, so that's 1 bit for each number from 0 to k, hence it uses
O( ceil( k / 8 ) )
bytes if you want to be pedantic. -
puneet over 9 yearsThe implementation ideone.com/jOOZX4
-
kap over 9 yearsCan you give some hint what you mean by that? Or a link to a definition of element uniqueness bit and to the reduction?