UVA 11057 - Exact Sum (Explanation)

Problem Explanation

Problem Category: Easy
Algorithm : Binary search

Explanation: You are given a list of numbers which represent money and total money that the boy get. Take one element from the list and find out other element by subtracting from total amount of money. Use binary search for searching the another element after subtracting. When you will find the two number you have to check if their difference is minimum.
You can do the same operation by using loop but in worst case you will get time complexity. 

Don't forget to sort the data 😜

Sudo code:

1. Take one element from the list. This one should be  a
2.  now b = total  - a where total is the money which the boy was given in two weeks
3. check if a is greater than b, that mean this a already have checked, if it is true just break
4. if not the search b using binary search
5. When you will found check if b-a is minimum
6.  if b-a is minimum then store it as lowa and lowb.
7. Remember, your answer actually lowa and lowb

Check some test case:
8
12 9 3 15 18 5 10 6
21
8
12 9 3 15 18 5 10 6
15
8
12 9 3 15 18 5 10 6
33

If you face trouble you can see the code. Just Click