2
\$\begingroup\$

I'm working on the problem of finding 2 numbers that their sum is closest to a specific number. Input numbers are not sorted.

My major idea is to sort the numbers and find from two ends. I'm wondering if there are any better ideas in terms of algorithm time complexity. Any advice of code bug and code style is appreciated.

import sys
def find_closese_sum(numbers, target):
    start = 0
    end = len(numbers) - 1
    result = sys.maxint
    result_tuple = None
    while start < end:
        if numbers[start] + numbers[end] == target:
            print 0, (numbers[start], numbers[end])
            return
        elif numbers[start] + numbers[end] > target:
            if abs(numbers[start] + numbers[end] - target) < result:
                result = abs(numbers[start] + numbers[end] - target)
                result_tuple = (numbers[start], numbers[end])
            end -= 1
        else:
            if abs(numbers[start] + numbers[end] - target) < result:
                result = abs(numbers[start] + numbers[end] - target)
                result_tuple = (numbers[start], numbers[end])
            start += 1

    return result, result_tuple

if __name__ == "__main__":
    numbers = [2,1,4,7,8,10]
    target = 16
    numbers = sorted(numbers)
    print find_closese_sum(numbers, target)
\$\endgroup\$
  • 1
    \$\begingroup\$ Have you ran pylint on this? I have mentioned this in a couple of answers for your questions. \$\endgroup\$ – Dair Dec 28 '16 at 5:25
  • \$\begingroup\$ @Dair, I am using Pycharm and it automatic alerts any non-PEB8 issues, I have fixed major issues, and for other issues, I think it might be too much overhead or minor for this problem. If I read the PEB8 alerts wrong, please feel free to correct me. Thanks. \$\endgroup\$ – Lin Ma Dec 29 '16 at 5:54
4
\$\begingroup\$

Your approach is good. Improvement you can do is use a better sorting technique and rest the approach you are using seems best one.

  1. Sort all the input numbers (Use better sorting techniques Eg. Quicksort).
  2. Use two index variables l and r to traverse from left and right ends respectively. Initialize l as 0 and r as n-1.
  3. sum = a[l] + a[r]
  4. If sum is less than number, then l++
  5. If sum is greater than number, then r–-.
  6. Keep track of min sum
  7. Repeat steps 3, 4, 5 and 6 while l < r.

Time complexity: complexity of quick sort + complexity of finding the optimum pair

= O(nlogn) + O(n) = O(nlogn)
\$\endgroup\$
  • 1
    \$\begingroup\$ You can't really say if quicksort is better then Timsort (which is used in python sorted). Timsort is guaranteed to be nlogn quicksort is n^2 in a worst case, but space complexity is better for quicksort. \$\endgroup\$ – Alex Dec 28 '16 at 15:37
  • \$\begingroup\$ @Alex, nice catch, I am not aware Python sort function is not using quick sort. \$\endgroup\$ – Lin Ma Dec 29 '16 at 5:55
  • \$\begingroup\$ Thanks Abhishek, good advice and vote up. For sorted in Python 2.7, is it using quick sort or not, or implementation (e.g. I am using Python 2.7, but miniconda other than standard C-Python)/patch specific? My original thought is sorted should use quick sort, but if I am wrong, please feel free to correct. If you could refer the specific sorting algorithm used with official reference, it will be great. \$\endgroup\$ – Lin Ma Dec 29 '16 at 5:56
  • 1
    \$\begingroup\$ If you are using python sort function then its good, else quicksort is to be used. In the worst case, Timsort takes {Theta (n\log n)}), one of best sorting algo also it is adaptive. \$\endgroup\$ – Abhishek Gupta Dec 29 '16 at 6:16
  • \$\begingroup\$ Thanks for all the help Abhishek, mark your reply as answer. \$\endgroup\$ – Lin Ma Jan 15 '17 at 4:56
2
\$\begingroup\$

There is no need for elif: the if clause contains return. Once you remove it, you may immediately simplify the code by lifting the copy-pasted lines out of the conditional. Consider

    if numbers[start] + numbers[end] == target:
        print 0, (numbers[start], numbers[end])
        return

    if abs(numbers[start] + numbers[end] - target) < result:
        result = abs(numbers[start] + numbers[end] - target)
        result_tuple = (numbers[start], numbers[end])

    if numbers[start] + numbers[end] > target:
        end -= 1
    else:
        start += 1

The function does both return and return result, result_tuple. This confuses both caller and the reviewer. Did you test the code with the exact sum testcase?

\$\endgroup\$
  • \$\begingroup\$ Hi vnp, I read through your code. I think your code has issue since it only returns when there is exact match, how your code handle if there is no exact match answer, but an approximate match? \$\endgroup\$ – Lin Ma Dec 29 '16 at 5:54
  • 1
    \$\begingroup\$ @LinMa I addressed the return issue in the second paragraph. Just return what you did in your code, but don't forget to return a meaningful result in case of exact match. \$\endgroup\$ – vnp Dec 29 '16 at 6:13
  • \$\begingroup\$ Thanks vnp, agree with your comments of 2nd paragraph using both return and print is confusing. But I am talking something else issue in your code, for a test case ` numbers = [2,1,4,7,8,10]` and target = 16, we should return result (7,10) which is not exact 16, but the sum most near 16. I do not think your code handles this case, since you return or print only when sum of two numbers are exactly the same as target. If I read your code wrong, please feel free to correct me. \$\endgroup\$ – Lin Ma Dec 30 '16 at 1:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.