[Algorithm] Largest Number

Largest Number

Problem statement

Given a list of non negative integers, arrange them such that they form the largest number.

For example, given [3, 30, 34, 5, 9], the largest formed number is 9534330.

Note: The result may be very large, so you need to return a string instead of an integer.

Solution: sorting

This is sort of global optimization problem. If we can find a local solution for optimization we can satisfy the global constraint.

Let's try some scenarios to find out the rules to order those numbers. First we start with simple scenarios.

Given two numbers [x, y] how can we form the largest number, we need to compare whether number xy is greater than yx. This is straightforward enough, then how about 3 numbers [x, y, z]?

Suppose 3 numbers are [3, 30, 34], the largest number is 34330. We can observe that the ordering [34, 3, 30]  follows the rule described for the two number scenarios for each pair of numbers. The local optimization of two numbers could be applied to the global optimization. So if we can keep the order of numbers as to form the largest number between each pair of numbers in the set then we can find the largest number consists of the whole set.

So the solution is to sort the whole set by order of [x, y] where xy > yx for each pair of numbers.

The implementation is the following:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33

class Solution { public: string largestNumber(vector<int>& nums) { if (nums.empty()) return ""; sort(nums.begin(), nums.end(), comp); string largest; if (nums[0] == 0) return "0"; for (auto v : nums) { ostringstream ostr; ostr << v; largest += ostr.str(); } return largest; } static inline long long catNum(int lhs, int rhs) { if (rhs == 0) return lhs*10; int tmp = rhs; long long base = 1; while (tmp) { tmp /= 10; base *= 10; } return (lhs*base + rhs); } static bool comp(int a, int b) { long long ab = catNum(a, b); long long ba = catNum(b, a); return (ab > ba); } };