Problem 🤔
Given an array of 2n integers, your task is to group these integers into n pairs of integer, say (a1, b1), (a2, b2), …, (an, bn) which makes sum of min(ai, bi) for all i from 1 to n as large as possible.
Input: [1,4,3,2] Output: 4 Explanation: n is 2, and the maximum sum of pairs is 4 = min(1, 2) + min(3, 4).
Code
def quickSort(self,nums, low, high): if low < high: part = self.partition(nums, low,high) self.quickSort(nums,low,part-1) self.quickSort(nums,part+1,high) def partition(self, nums, low, high): i = (low - 1) pivot = nums[high] for j in range(low, high): if nums[j] <= pivot: i += 1 nums[i],nums[j] = nums[j],nums[i] nums[i+1],nums[high] = nums[high],nums[i+1] return(i+1) def arrayPairSum(self, nums): temp = 0 self.quickSort(nums,0,len(nums)-1) for index in range(0,len(nums)-1,2): temp += min(nums[index],nums[index+1]) return temp
Developer’s Notes 👨💻
For this I ordered the list using a quicksort, then I cycled through the array took the pairs of numbers and summed the mins. I ordered the array since it would give the largest possible minimum for each pair.
Developer: Austin 