Find Three Unique Elements from List Whose Sum is Closest to K in Python

Suppose we have a list of numbers called nums and another value k, we have to find three unique entries in nums (a, b, c) such that |a + b + c − k| is minimized and return the absolute difference.

So, if the input is like nums = [2, 5, 25, 6] k = 14, then the output will be 1 as if we take [2, 5, 6] will get us closest to 14 and the absolute difference is |13 − 14| = 1.

To solve this, we will follow these steps −

• sort the list nums

• ans := 1^9

• for i in range 0 to size of nums, do

  • j := i + 1

  • k := size of nums − 1

  • while j < k, do

    • s := nums[i] + nums[j] + nums[k]

    • if s <= target, then

      • ans := minimum of ans and target − s

      • j := j + 1

    • otherwise,

      • ans := minimum of ans and s − target

      • k := k − 1

• return ans

Let us see the following implementation to get better understanding −

Example

 Live Demo

class Solution:
   def solve(self, nums, target):
      nums.sort()
      ans = 1e9
      for i in range(len(nums)):
         j = i + 1
         k = len(nums) − 1
         while j < k:
            s = nums[i] + nums[j] + nums[k]
            if s <= target:
               ans = min(ans, target - s)
               j += 1
            else:
               ans = min(ans, s - target)
               k −= 1
      return ans
ob1 = Solution()
nums = [2, 5, 25, 6]
k = 14
print(ob1.solve(nums, k))

Input

[2, 5, 25, 6], 14

Output

1