Zed - 4 months ago 22

Java Question

I am trying to solve a really interesting programming challenge and I'm sort of out of the ideas why my code fails. Here it is:

Write a function that, given a list and a target sum, returns

zero-based indices of any two distinct elements whose sum is equal to

the target sum. If there are no such elements, the function should

return null.

For example, findTwoSum(new int[] { 1, 3, 5, 7, 9 }, 12) should return any of the following tuples of indices:

`1, 4 (3 + 9 = 12)`

2, 3 (5 + 7 = 12)

3, 2 (7 + 5 = 12)

4, 1 (9 + 3 = 12)

Should be simple right? So here's my function:

`public static int[] findTwoSum(int[] list, int sum) {`

int[] indices = null;

for(int i = 0; i < list.length; i++) {

int currentNum = list[i];

int findNum = sum - currentNum;

int length = list.length;

int min = i;

int max = length-1;

while(max >= min) {

int guess = (max+min)/2;

if(list[guess] == findNum) {

return new int[] {i,guess};

}

if(list[guess] < findNum) {

min = guess + 1;

}

if(list[guess] > findNum) {

max = guess - 1;

}

}

}

return indices;

}

Code is pretty simple, for every element in the array, it tries to find using binary search, another element, so that their sum is equal to the provided

`sum`

Answer

The code assumes that the list is sorted. The problem statement does not say anything about the order of elements, so you need to sort the array yourself. Since you need indexes, you need to sort pairs of values and indexes.

A faster approach is to put the data into a hash map with counts and original indexes, and check for presence of `Target - n`

for each `n`

in the list. You need counts for the special case when `Target`

is equal to `2*n`

.