AKIWEB - 5 months ago 32x

Java Question

Suppose you are given an array of unsorted integers as

`A = {3,4,5,1,4,2}`

Input :

`6`

Output :

`{5,1}, {4,2}`

How can I do this in O(n) or O(log n). Any suggestions will be appreciated.

Can we write something more efficient than this?

`for(int i=0;i<array.length-1;i++)`

{

if(array[i]+array[i+1]==6)

System.out.println("{"+array[i]+","+array[i+1]+"}");

}

Answer

If the numbers stored in the input array are only positive then I'd create another array K of k+1 ArrayList elements. Where k is the number you need them to add up to. Only two numbers less than k can add up to k (assuming we deal with positive ints} or in special case {0,k}. Then I would iterate through all elements of input array and for each int m that is less or equal to k I'd take its index and add that index to the array of ArrayList K at index m. Then I would iterate through first half of the array K and for each index i that has some ints stored in it I would find complementary index [k-i] and see if there are any values in it. If there are then those are your pairs. And btw this is O(n).

```
public static void findElemtsThatSumTo( int data[], int k){
List arrayK[]= new List[k+1];
for(int i=0; i<arrayK.length; i++)
arrayK[i]= new ArrayList<Integer>();
for(int i=0; i<data.length; i++){
if(data[i]<=k)
arrayK[data[i]].add(i);
}
for(int i=0; i<arrayK.length/2; i++){
if(!arrayK[i].isEmpty() && !arrayK[k-i].isEmpty())
{
for(Object index: arrayK[i])
for(Object otherIndex: arrayK[k-i])
System.out.println("Numbers at indeces ["+index.toString()+", "+otherIndex.toString()+"] add up to "+k+".");
}
}
}
```

Source (Stackoverflow)

Comments