1-liner Python and 4-liner C++ with rigorous proof (Triangle Inequality!)


  • 0

    As many has posted here, the answer is simply to sum up the 2nd, 4th, 6th, ...largest values from nums[]. But why?

    The problem ca be reduced to prove the following statement:
    Let

    • P be an arbitrary n-pair partition for nums[],
    • sum(P) be such sum of partition P,
    • max1, max2 be the max and 2nd max values in nums[].

    Prove if max1 is not paired with max2 in P, and we swap max2 with the value paired with max1 to get partition P', we must have
    sum(P') >= sum(P).

    Proof: Without losing generality, let pairs (max1, v1) and (max2, v2) in partition P and v1 < max2, then P' has the same pairs as P except (max1, max2) and (v1, v2). We will only need to prove that
    min(max1, max2) + min(v1, v2) >= min(max1, v1) + min(max2, v2).

    Note that min(x, y) = (x+y-|x-y|)/2 for any number x, y, so we can simplify the inequality above as
    max2 - v1 >= min(max2, v2) - min(v1, v2) = (max2+v2-|max2-v2|-(v1+v2-|v1-v2|))/2
    = (max2-v1 + |v1-v2| - |max2-v2|)/2.

    By triangle inequality, actually, the right hand side
    (max2-v1 + |v1-v2| - |max2-v2|)/2 <= (max2-v1 + |max2-v1|)/2 = max2 - v1.
    And the proof is complete.

    Python:

        def arrayPairSum(self, nums):
            return sum(sorted(nums)[::2])
    

    C++:

        int arrayPairSum(vector<int>& nums) {
            sort(nums.begin(), nums.end());
            int sum = 0, i = 1;
            for (int x : nums) sum += x*(i++%2);
            return sum;
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.