In order to run this program, a java runtime environment must be installed (tested with version 10).
Please, run the following command
./buildPlease, run the following command specifying a string argument
./k-complementary
- On first attempt a simple nested loop was implemented
int count = 0;
for (int i = 0; i <= array.length - 1; i++) {
for (int j = 0; j <= array.length - 1; j++) {
if (i!=j && array[i] + array[j] == k) {
count++;
}
}
}
return count / 2;- Second attempt:
I have realized that sencond loop is used to just locate a specific integer, there is no need to scan an array to find elements, we can use some data structures. If we run across the array and put all the elements in a Set (or hashmap to keep the elements count) we can easily check if the number matching the condition is present,
e[i] + e[j] = k =>
e[j] = k - e[i]
hash access is based on index. Of course it will have impact in memory but will reduce complexity and process time. lets give a try. The problem is that I cant know if the number I am looking for is the same number I am now, for example, given the array {2} with k=4, this algorithm returns 1, or worst the array {2,2,2,2} with k=4 returns 16!
Update: I managed to fix thi issue, however the resulting algorithm didnt handle properly the situation when duplicate pairs i,j were present, I have isolated this in the test testKComplementaryDuplicates. As long as I coundt finish the improvement I consider this trial failed :( I levae the code in a separate method countComplementariesTrial for illustration.
First approach has to loop over the whole array for each elements which leads to an O(n^2) complexity. Even if we improved the algorithm by not chacking twice the comparisons already done the algorithm would have little improvement in terms of efficiency.
As I mentioned before the complexity O(n^2) could be improved by a better algorithm, probably up to O(n) at a higher memory cost.