Ctrl K

Biggest Number Divisible by Three

Hard
You have a set of cards, each showing a single digit, given as the array cards. Lay out some of them in a row (all or only a few, in any order) to form the largest possible number that is divisible by 3. Return that number as a string, since it can be very long. It must not have unnecessary leading zeros: for instance, a row of zeros is just "0". If no such number can be formed, return an empty string.
Example 1
cards=[4, 7, 2] → '72'

All three digits sum to 13, which is not divisible by 3. Dropping either 4 or 7 fixes that; dropping 4 leaves the larger number, 72.

Example 2
cards=[5, 0, 0, 8, 1] → '8100'

The sum is 14, remainder 2. Removing the smallest digit with remainder 2, which is 5, leaves 8, 1, 0, 0 and the number 8100.

Example 3
cards=[0, 0, 0] → '0'

Only zeros are available, so the answer is a single 0 with no extra leading zeros.

Constraints
  • 1 ≤ len(cards) ≤ 10⁴
  • 0 ≤ cards[i] ≤ 9
Have you seen this problem in a real interview?
Solved by0
Tried by0
Submissions0
Acceptance—
Topics
Similar problemsBest Order for a Tasting Menu HardParcel Lockers Along a Road HardTotal Strength of All Squads HardGrowing Groups Without Repeats HardEdge Toggles on a Tree Hard
loading Python…
Input
cards=[4, 7, 2]
Expected
'72'

Run checks the first 3 tests in your browser. Submit checks all 75 tests on the server, hidden ones included.