Largest Number Solution for Accenture
Company: Accenture · Difficulty: Medium · Topics: String, Greedy, Sorting
Problem Statement
Given a list of non-negative integers nums, arrange them such that they form the largest number and return it.
Since the result may be very large, return it as a string.
Key Understanding:
- Arrange numbers to form the largest possible number
- Compare numbers as strings, not as integers
- Handle edge cases like all zeros
- Return result as string
- The order of concatenation matters for creating the largest number
Examples
Example 1:
Input: nums = [10,2]
Output: "210"
Explanation:
- Option 1: "10" + "2" = "102"
- Option 2: "2" + "10" = "210"
- 210 > 102, so we choose "210"
Example 2:
Input: nums = [3,30,34,5,9]
Output: "9534330"
Explanation:
- Step-by-step comparison:
- Compare "3" vs "30": "330" vs "303" → "330" > "303" → 3 comes before 30
- Compare "30" vs "34": "3034" vs "3430" → "3430" > "3034" → 34 comes before 30
- Compare "34" vs "5": "345" vs "534" → "534" > "345" → 5 comes before 34
- Compare "5" vs "9": "59" vs "95" → "95" > "59" → 9 comes before 5
- Final order: [9, 5, 34, 3, 30] → "9534330"
Example 3:
Input: nums = [1]
Output: "1"
Explanation:
- Single number, no arrangement needed
- Result: "1"
Example 4:
Input: nums = [10]
Output: "10"
Explanation:
- Single number, no arrangement needed
- Result: "10"
Example 5:
Input: nums = [0,0]
Output: "0"
Explanation:
- Both numbers are 0
- Result would be "00", but we return "0" (no leading zeros)
Example 6:
Input: nums = [3,30,34,5,9,0]
Output: "95343300"
Explanation:
- 0 will be placed at the end since "30" < "03" for any number
- Final order: [9, 5, 34, 3, 30, 0] → "95343300"
Intuition
The key insight is to compare numbers as strings, not as integers. When comparing two numbers, we need to determine which order gives us a larger result.
Why String Comparison Works:
- When we concatenate numbers, the order matters
- "3" + "30" = "330" vs "30" + "3" = "303"
- "330" > "303", so 3 should come before 30
- This is not the same as integer comparison (3 < 30)
Custom Comparator Logic:
- For numbers a and b, compare "ab" vs "ba"
- If "ab" > "ba", then a should come before b
- If "ab" < "ba", then b should come before a
- If "ab" == "ba", then order doesn't matter
- This ensures we get the largest possible concatenated number
Approach
Approach 1: Custom Sorting with qsort (Optimal)
Algorithm:
1. Convert all numbers to strings
2. Sort using custom comparator: strcmp("ab", "ba")
3. Join all strings in sorted order
4. Handle edge case: if result starts with "0", return "0"
Custom Comparator:
- Convert numbers to strings
- Concatenate in both orders: "ab" and "ba"
- Compare using strcmp
- Return reverse order for descending sort
Approach 2: Bubble Sort with Custom Comparison
Algorithm:
1. Use bubble sort with custom comparison function
2. Compare concatenated strings at each step
3. Swap elements if needed
4. Join result strings
Approach 3: Permutation Generation (Educational)
Algorithm:
1. Generate all possible permutations
2. Convert each permutation to string
3. Find the largest string
4. Return the result
Dry Run
Let's trace through Example 2: nums = [3,30,34,5,9]
Step-by-Step Sorting Process:
1. Initial array: [3, 30, 34, 5, 9]
2. Compare 3 vs 30:
- "330" vs "303"
- "330" > "303" ✓
- Order: [3, 30, 34, 5, 9]
3. Compare 30 vs 34:
- "3034" vs "3430"
- "3430" > "3034" ✓
- Order: [3, 34, 30, 5, 9]
4. Compare 34 vs 5:
- "345" vs "534"
- "534" > "345" ✓
- Order: [3, 5, 34, 30, 9]
5. Compare 5 vs 9:
- "59" vs "95"
- "95" > "59" ✓
- Order: [3, 9, 5, 34, 30]
6. Continue sorting...
- Final order: [9, 5, 34, 3, 30]
7. Result: "9534330"
Edge Case: All Zeros
Input: [0, 0, 0]
- Sorted order: [0, 0, 0]
- Result: "000"
- Handle edge case: Return "0"
Key Insights
1. String vs Integer Comparison: "3" + "30" ≠ "30" + "3"
2. Custom Comparator: Compare concatenated strings, not individual numbers
3. Descending Order: We want the largest number, so sort in descending order
4. Leading Zeros: Handle case where result would have leading zeros
5. Stability: The sorting algorithm should be stable for consistent results
6. Edge Cases: Single element, all zeros, mixed zeros
Edge Cases
1. Single Element: Return the number as string
2. All Zeros: Return "0" (not "000...")
3. Mixed Zeros: Zeros should be placed appropriately
4. Large Numbers: Handle efficiently without overflow
5. Equal Numbers: Order doesn't matter for equal numbers
6. Empty Array: Return empty string (though constraints say length ≥ 1)
Solution
⚠️ Disclaimer: Don't jump directly to the solution, try it out yourself first. Only look at the solution after you've given it a good attempt.
Solution 1: Custom Sorting with qsort (Optimal)
Time Complexity: O(n log n * k) where k is average string length
Space Complexity: O(n * k) for string storage
Solution 2: Bubble Sort with Custom Comparison
Time Complexity: O(n² * k)
Space Complexity: O(n * k)
Solution 3: Permutation Generation (Educational)
Time Complexity: O(n! * n * k)
Space Complexity: O(n * k)