Sort-based solution and correctness proof


  • 0
    J
    class Solution {
    public:
        string largestNumber(vector<int>& nums) {
            // define the order of a1 and a2: 
            // a1 > a2 if a1a2 > a2a1
            // a1 = a2 if a1a2 = a2a1
            // a1 < a2 if a1a2 < a2a1
            //
            // for example:
            // 34 > 30 because 3430 > 3034
            // 33 = 3  because 333  = 333
            // 34 < 9  because 349  < 934
            //
            // if a1 >= a2 >= ... >= an, then a1a2...an is the largest number
            // we can prove it by contradiction
            //
            // assume exists i and j, satisfy:
            // i < j and a1a2...ai...aj...an < a1a2...aj...ai...an
            // let ak be the number formed by the numbers between ai and aj
            // by the assumption, there must be aiakaj < ajakai
            //
            // for simplify, if a1 > a3, and we just need prove that a1a2a3 > a1a2a3
            // let:
            // the length of a1 is l1
            // the length of a2 is l2
            // the length of a3 is l3
            // 
            // we have:
            // a1a3 > a3a1 => 10^l3 * a1 + a3 > 10^l1 * a3 + a1
            // a2a3 > a3a2 => 10^l3 * a2 + a3 > 10^l2 * a3 + a2
            // a1a2 > a2a1 => 10^l2 * a1 + a2 > 10^l1 * a2 + a1
            //
            // => 10^l2 * (10^l3 * a1 + a3) + (10^l3 * a2 + a3) + (10^l2 * a1 + a2) > 10^l2 * (10^l1 * a3 + a1) + (10^l2 * a3 + a2) + (10^l1 * a2 + a1)
            // => 10^l2 * (10^l3 * a1 + a3) + (10^l3 * a2 + a3) + (10^l2 * a1 + a2) > 10^l2 * (10^l1 * a3 + a1) + (10^l1 * a2 + a1) + (10^l2 * a3 + a2) 
            // => 10^l2 * (10^l3 * a1 + a3) + (10^l3 * a2 + a3) + 10^l2 * a1 > 10^l2 * (10^l1 * a3 + a1) + (10^l1 * a2 + a1) + 10^l2 * a3          
            // => 10^l2 * (10^l3 * a1 + a3) - 10^l2 * a3 + (10^l3 * a2 + a3) > 10^l2 * (10^l1 * a3 + a1) - 10^l2 * a1 + (10^l1 * a2 + a1)
            // => 10^(l2+l3) * a1 + 10^l3 * a2 + a3 > 10^(l2+l1) * a3 + 10^l1 * a2 + a1
            // => a1a2a3 > a3a2a1
    
            // sort by descending order
            sort(nums.begin(), nums.end(), Solution::compare);
            
            // form the largest number
            string result;
            for (const auto &num : nums) {
                result += to_string(num);
            }
            
            // if nums are composed by all zeros, the result should be "0"
            size_t pos = result.find_first_not_of('0');
            if (pos == string::npos) return "0";
    
            return result;
        }
        
    private:
        static bool compare(int num1, int num2) {
            return to_string(num1) + to_string(num2) > to_string(num2) + to_string(num1);
        }
    };

Log in to reply
 

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