beta

Practice problem · medium

Largest number from the pieces

Lesson: Comparators in four languages~25 min

Payments apppractice problem 20 of the lessonup to 35 Bits0/5 hints open

Scenario

A payments app runs a bonus draw. Each customer owns several receipt numbers. The customer may write them one after another in any order, with no spaces, to make one long number. The biggest number wins.

You get the receipt numbers of one customer. Find the biggest number they can make.

Your task

Write largest_number(pieces).

pieces[i] is a receipt number, a whole number from 0 up.
Join all the pieces, each written in ordinary digits, in the order that makes the largest number.
Return that number as a string, because it can have hundreds of thousands of digits. If every piece is 0, return "0".

Examples

Example 1 (traced)#

text2 lines

Input:  pieces = [3, 30, 34, 5, 9]
Output: "9534330"

Put piece a before piece b when the text a + b is larger than b + a. Compare the joined texts, not the numbers themselves.

Pair	a + b	b + a	Order
3 and 30	330	303	3 first
34 and 3	343	334	34 first
9 and 5	95	59	9 first

Sorted by that rule the pieces read 9, 5, 34, 3, 30, which joins to 9534330.

Example 2#

text2 lines

Input:  pieces = [10, 2]
Output: "210"

210 is larger than 102, so 2 goes before 10.

Example 3#

text2 lines

Input:  pieces = [0, 0]
Output: "0"

Joining gives 00, which is the number 0, written as "0".

Constraints

1 ≤ pieces.length ≤ 50,000
0 ≤ pieces[i] ≤ 1,000,000,000
The result can have up to 500,000 digits, so it is a string.

What does n ≤ 5 × 10^4 tell you?

Trying every order means n! orders, and 20 pieces already have more than 2 × 10^18. You need a sort, which costs about n log n comparisons. Each comparison joins two short strings, so it costs a handful of steps.

write largest_number · runs in your browser

Loading the editor…

Run tries the examples · Submit checks every test

Coding is easiest on a laptop. On a phone, read, trace and try small edits.

Practice problem · medium

Largest number from the pieces

Lesson: Comparators in four languages~25 min

Payments apppractice problem 20 of the lessonup to 35 Bits0/5 hints open

Scenario

You get the receipt numbers of one customer. Find the biggest number they can make.

Your task

Write largest_number(pieces).

pieces[i] is a receipt number, a whole number from 0 up.
Join all the pieces, each written in ordinary digits, in the order that makes the largest number.
Return that number as a string, because it can have hundreds of thousands of digits. If every piece is 0, return "0".

Examples

Example 1 (traced)#

text2 lines

Input:  pieces = [3, 30, 34, 5, 9]
Output: "9534330"

Put piece a before piece b when the text a + b is larger than b + a. Compare the joined texts, not the numbers themselves.

Pair	a + b	b + a	Order
3 and 30	330	303	3 first
34 and 3	343	334	34 first
9 and 5	95	59	9 first

Sorted by that rule the pieces read 9, 5, 34, 3, 30, which joins to 9534330.

Example 2#

text2 lines

Input:  pieces = [10, 2]
Output: "210"

210 is larger than 102, so 2 goes before 10.

Example 3#

text2 lines

Input:  pieces = [0, 0]
Output: "0"

Joining gives 00, which is the number 0, written as "0".

Constraints

1 ≤ pieces.length ≤ 50,000
0 ≤ pieces[i] ≤ 1,000,000,000
The result can have up to 500,000 digits, so it is a string.

What does n ≤ 5 × 10^4 tell you?

write largest_number · runs in your browser

Loading the editor…

Run tries the examples · Submit checks every test

Coding is easiest on a laptop. On a phone, read, trace and try small edits.