Coming from an engineering background I want to solve this question.
Question:
Given a set of positive, and negative numbers, how do I time optimally find two numbers whose sum is the mathematical negative of a third number?
Breakdown of question:
I have isolated two keywords, dynamic programming and number partitioning (number theory) and a reference to this hard problem
I believe the solution might require a use of a 2d, or 3d indexed structure whose indices go from 0 -> minimum cubic value from the max value in the set, and use that indexed structure to find relevant information
Determine if a set has three integers that add to zero, in some time, that has been sub-optimally determined to be N squared, for all possible combinations of pairs of numbers to be selected, to be compared to a third.
I reduced it to read as such.
1)Find all two numbers in a sub quadradic computation time.
2)Find all the corresponding third number that cancels or doubles the value
But how... so I divided the problem further... Find a way to represent numbers graphically that adds up and came up with some approaches.
- Use the set but create a copy, like in a computer so that it will operate like a shift register from start to finish, while forgetting duplicates
- Remains the question of storage, what computing data structure would accomplish remembering what I have, and that is where I stopped
- I considered using a space possibly inefficient 3D representation of the numbers like an Octree to solve this, because I can sparsely specify data points to be stored based on criteria x,y,z, but do I need to have a large space allocated for this structure that for my number set based on my set's max number's number of digits for all numbers
- How can I exploit mathematical laws of numbers 0-9 to optimize determination of the two values to pick from the array, some how, like a linkage or another set of numbers
- How do I process the numbers faster, as this is already solved in computer science, by means of linear time sorting algorithms like Radix Sorting, with a Binary Search algorithm.
*) Finding the last number is a matter of either adding to double the sum, or diving by a 1st power 2 to get (shift right in computer arithmetic) to equal the average of the two numbers added together
Do any of these approaches solve this problem of finding a number whose sum is 0, whose absoluteValue(a+b) equals c, or avg(abs(a+b)) = c >> 2;
Any suggestions to help in moving me forward would be tremendously appreciated.
Thank You.