# Apex Coding Challenge for Iterating Lists

Here is the problem statement:

Given an expectedSum value find the sum (n+ (n+1) = expectedValue) from a list that equals the expectedSum. I am using the following list

1,3,4,4,5,9

and looking for the sum to be 8 (3+5, 4+4)

*Note the list is sorted

Solution 1:

```
Integer expectedSum = 8;
List<Integer> listInts = Arrays.asList(1,3,4,4,5,9);

for (Integer k=0; k<listInts.size();k++){
for (Integer j=k+1; j<listInts.size();j++){
if (listInts.get(k)+listInts.get(j)==expectedSum){
System.debug(listInts.get(k) + ' + ' + listInts.get(j));
}
}
}

```

The above time complexity for a nested for loop is O(n^2)

Solution 2:

Do a binary search to search if the diff is contained in the list

```
Integer expectedSum = 8;
List<Integer> listInts = Arrays.asList(1,3,4,4,5,9);
for (Integer listInt : listInts){
Integer diffInt = expectedSum-listInt;
if (binarySearch(listInts, diffInt)!=null){
System.debug(listInt + " + " + diffInt);
}
}

public static Integer binarySearch(List<Integer> listInts, Integer searchInt){
Integer startPos = 0;
Integer listSize = listInts.size() - 1;
Integer mid;
while(startPos <= listSize){
mid=(startPos+listSize)/2;
if(listInts.get(mid) == searchInt){
return listInts.get(mid);
}
else if(searchInt < listInts.get(mid)){
listSize = mid - 1;
}
else{
startPos = mid + 1;
}
}
return null;
}

```

the above time complexity for binary search is for each element in the array O(n log n) Returning null is not a good practice try to return another number or throw an exception.

Solution 3:

Check if the diff is contained in the list by using the .contains method

```
Integer expectedSum = 8;
List<Integer> listInts = Arrays.asList(1,3,4,4,5,9);

for (Integer listInt : listInts){
Integer diffInt =expectedSum-listInt;
if (listInts.contains(diffInt)){
System.debug(listInt + ' + ' + diffInt);
}
}

```

the above time complexity for loop is O(n)

Option 4

Start on either end of the array and move inwards when you find a solution, if the sum of the outer and inner element is bigger that the expectedSum move the maxPointer inwards, if it is smaller move the minPointer inwards.

```        Integer expectedSum = 1;
List<Integer> listInts = Arrays.asList(1,3,4,4,5,9);

Integer maxPointer = listInts.size()-1;
Integer minPointer = 0;
for (Integer k=0; k<listInts.size();k++){
if (expectedSum < listInts.get(maxPointer)){
maxPointer-=1;
} else if (minPointer!=maxPointer){
Integer sumPair =listInts.get(minPointer) + listInts.get(maxPointer);
if ( sumPair == expectedSum){
System.debug(listInts.get(minPointer) + " + " + listInts.get(maxPointer));
minPointer +=1;
maxPointer-=1;
} else if (sumPair < expectedSum){
minPointer +=1;
} else {
maxPointer-=1;;
}
}

}

```

the above time complexity for loop is O(n)

Output:

```4 + 4
5 + 3
3 + 5
```

Bonus:

How to do it with an unsorted list:

Iterate through the list and add the integer to the list, if the diff of the expected sum and integer is contained in the set then print it

```		Integer expectedSum = 8;
List<Integer> listInts = Arrays.asList(7,4,6,1,5,2,3);

Set<Integer> intSetWithDiff = new HashSet<>();
for (Integer listInt : listInts){
Integer sumDiff = expectedSum - listInt;

if (intSetWithDiff.contains(sumDiff)){
System.debug(listInt + " + " + sumDiff);
}
```1 + 7