Biggest Number From Cards
In a family card game, each player is dealt a few cards with whole numbers printed on them, like 7, 60 and 65. You lay all your cards side by side in a row, and the digits read left to right form one big number. Biggest number wins the round.
Cards cannot be cut or turned over, only reordered. Your cousin keeps putting the card with the biggest value first and keeps losing. Work out the best row.
Your task
Write largestNumber(cards). Return, as a string, the largest number you can form by placing all the cards in some order and joining their digits.
Return the result without extra leading zeros: if every card is 0, return "0", not "000". Return a string because the result can have hundreds of digits.
largestNumber(cards: int[]) → string
Examples
cards = [7, 60, 9, 65]
"976560"
Putting the largest card first gives 65 60 9 7 = "656097", which loses. A 9 at the front beats any 6, so 9 goes first, then 7, then 65 before 60. Result "976560".
cards = [34, 3, 31]
"34331"
Where does the lone 3 go? Before 34 gives "334…", after it gives "343…", so 34 first. Between 3 and 31: "331" beats "313", so 3 goes before 31. Result "34331".
Constraints
- 1 ≤ cards.length ≤ 100
- 0 ≤ cards[i] ≤ 1,000,000,000
Start with brute force
Try every order of the cards, join each one, and keep the biggest. With 10 cards that is 3,628,800 orders; with 20 it is about 2.4 × 10¹⁸. Hopeless.
The quick guesses fail too. Sorting by numeric value puts 10 before 2 and builds "102" instead of "210". Sorting the strings in reverse dictionary order puts "121" before "12" and builds "12112" instead of "12121".
Hints
0 of 4 shown- Hint 1
Take just two cards, 3 and 31. Which order wins, and how can you tell without thinking about any other card?
- Hint 2
Glue them both ways and compare: "331" vs "313". The bigger string decides which card goes first. That works for any pair, even when the cards have different lengths.
- Hint 3
If you can decide the order of any two cards, you have a comparison rule, and any sorting algorithm can use it. It never contradicts itself (if a beats b and b beats c, then a beats c), so a sort can use it safely.
- Hint 4
Turn the cards into strings. Sort with the rule:
agoes beforebifa + b > b + aas strings. Join them. If the result starts with "0", every card was 0, so return "0".
Walkthrough and solution
Unlocks when you pass every test. Stuck for a while? Looking is fine too, as long as you then close it and write the code yourself.
How to solve it
You cannot rank a card by itself: whether 3 should come before 31 depends on how their digits interleave. But you can always rank a pair by gluing them both ways. Hand that pair rule to a sort, and the sort finds the best row.
Trace the comparisons on [34, 3, 31] (strings "34", "3", "31"):
- "34" vs "3": "343" > "334", so 34 goes before 3.
- "3" vs "31": "331" > "313", so 3 goes before 31.
- "34" vs "31": "3431" > "3134", so 34 goes before 31.
- Sorted order: 34, 3, 31. Joined: "34331".
Comparing the two glued strings is safe even though they are digit strings, not numbers: a + b and b + a always have the same length, so string order and numeric order agree.
Why can a pairwise rule be trusted to give the best overall row? If two neighbours in some row were in the "wrong" order by this rule, swapping them would make the whole number bigger, because the digits before and after them stay put. So the best row has no such pair, which is exactly what the sort guarantees.
Finally, the zero case: [0, 0, 0] sorts to "000". If the first character is "0", the largest card is 0, so all cards are 0 and the answer is "0".
function largestNumber(cards) {
const parts = cards.map(String);
// a goes first if gluing a before b makes the bigger string
parts.sort((a, b) => {
const ab = a + b, ba = b + a;
if (ab > ba) return -1;
if (ab < ba) return 1;
return 0;
});
const result = parts.join('');
return result[0] === '0' ? '0' : result; // every card was 0
}from functools import cmp_to_key
def largest_number(cards):
parts = [str(c) for c in cards]
# a goes first if gluing a before b makes the bigger string
def compare(a, b):
if a + b > b + a:
return -1
if a + b < b + a:
return 1
return 0
parts.sort(key=cmp_to_key(compare))
result = ''.join(parts)
return '0' if result[0] == '0' else result # every card was 0Run your code to see results here. Run checks the examples. Submit checks every test, including hidden edge cases.