Solution For Largest Number
Problem Statement: Given a list of non-negative integers, arrange them such that they form the largest number.
Example:
Input: [3,30,34,5,9] Output: “9534330”
Solution:
To solve this problem, we need to create a custom sort function. Sort the numbers in the decreasing order based on the following comparison:
For any two numbers a and b, we compare the concatenation of a and b to the concatenation of b and a. If the former is greater than the latter, then a should come before b in the sorted array.
For example:
a=3, b=30
concatenation of a and b = “330”
concatenation of b and a = “303”
Since “330” is greater than “303”, a should come before b in the sorted array.
Using this custom sort, we can sort the list of numbers in descending order to form the largest number. Once we have sorted the numbers, we concatenate them to form the final result.
Code:
Here’s the Python code to solve this problem:
class Solution:
def largestNumber(self, nums: List[int]) -> str:
nums = [str(num) for num in nums]
nums.sort(key=lambda x: x + x[0], reverse=True)
return str(int(”.join(nums)))
Step by Step Implementation For Largest Number
class Solution { public String largestNumber(int[] nums) { // sort the array in reverse order Arrays.sort(nums, (a, b) -> (b + "" + a).compareTo(a + "" + b)); // if the first element is 0, return 0 if (nums[0] == 0) return "0"; // otherwise, combine all elements into a string StringBuilder sb = new StringBuilder(); for (int num : nums) sb.append(num); return sb.toString(); } }
class Solution: def largestNumber(self, nums: List[int]) -> str: # We need to sort the list in reverse order # and then join the elements to form a string return ''.join(sorted(map(str, nums), reverse=True))
var largestNumber = function(nums) { // sort the array in reverse order nums.sort((a, b) => { return b - a; }); // edge case: if the array contains only 0's if (nums[0] === 0) { return '0'; } // join the array and return it return nums.join(''); };
class Solution { public: string largestNumber(vector& nums) { // sort the array in reverse order sort(nums.rbegin(), nums.rend()); // if the first element is 0, the whole number must be 0 if (nums[0] == 0) { return "0"; } // otherwise, concatenate the numbers together string result = ""; for (int i = 0; i < nums.size(); i++) { result += to_string(nums[i]); } return result; } };
public class Solution { public string LargestNumber(int[] nums) { // Sort the array in reverse order Array.Sort(nums, (a, b) => b.ToString().CompareTo(a.ToString())); // If the first element is 0, the entire number will be 0 if (nums[0] == 0) { return "0"; } // Build up the final string StringBuilder sb = new StringBuilder(); foreach (int num in nums) { sb.Append(num); } return sb.ToString(); } }