You are given three arrays…You have to choose an element from first array and one from second array and check if their sum is in third array. if number of times we find sum in third array is greater than number of times we don’t find it then print “Yes” else “No”.
Any help will be appreciated.
most efficient algorithm with time complexity…please help!!!
@tmwilliamlin
@anon55659401
Provide problem link. And don’t tag people randomly.
1 Like
was asked by my data structures teacher in class…we proposed a n3 solution with three for loops but he said there is better solution with n2…can you help with that if you know
my approach is that-first go to every element of the first array then check its sum with elements with which we have not checked till yet and check if the sum is the 2nd array…and so on.
about tagging…I found these people helping others recently so tagged them
Iterate all pairs from arrays A and B , say , x=A[i]+B[j] , using a hashmap check if ‘x’ is present in array C or not .
1 Like
Assuming that you aren’t lying, it can be trivially optimised to O(n^2 log n) by mapping the elements of the third array to a boolean map which gives assured complexity of O(log n) lookup. You can use an unordered map for average O(1) lookup, so your code becomes O(n^2).
1 Like
well thanks…I will learn more about hashmaps and unordered sets. 
Oh Thanks for your help…I will learn more about maps and all stuff.
1 Like