# Участник:Easik/largest-multiple-of-three

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

Python

```class Solution(object):
def largestMultipleOfThree(self, digits):
"""
:type digits: List[int]
:rtype: str
"""

digit_sum = sum(digits)

# Trivial case
if digit_sum % 3 == 0:

digits = sorted(digits)[::-1]

if len(digits) == 0:
return ""

elif digits[0] == 0:
return "0"

else:
return "".join(str(d) for d in digits)

# Segregate digits by their remainders (% 3)
remainder_0 = []  # % 3 = 0
remainder_1 = []  # % 3 = 1
remainder_2 = []  # % 3 = 2

for d in digits:

if d % 3 == 0:
remainder_0.append(d)

elif d % 3 == 1:
remainder_1.append(d)

elif d % 3 == 2:
remainder_2.append(d)

valid_digits = []

# Remainder == 1
if digit_sum % 3 == 1:

if (len(remainder_1) > 0) and (len(remainder_2) > 1):

remainder_2 = sorted(remainder_2)
if min(remainder_1) <= sum(remainder_2[:2]):

idx = remainder_1.index(min(remainder_1))

valid_digits += remainder_0
valid_digits += remainder_1[:idx]
valid_digits += remainder_1[idx+1:]
valid_digits += remainder_2

else:

valid_digits += remainder_0
valid_digits += remainder_1
valid_digits += remainder_2[2:]

elif len(remainder_1) > 0:

idx = remainder_1.index(min(remainder_1))

valid_digits += remainder_0
valid_digits += remainder_1[:idx]
valid_digits += remainder_1[idx+1:]
valid_digits += remainder_2

elif len(remainder_2) > 1:

remainder_2 = sorted(remainder_2)

valid_digits += remainder_0
valid_digits += remainder_1
valid_digits += remainder_2[2:]

else:

valid_digits += remainder_0

assert sum(valid_digits) % 3 == 0
valid_digits = sorted(valid_digits)[::-1]

if len(valid_digits) == 0:
return ""

elif valid_digits[0] == 0:
return "0"

else:
return "".join(str(d) for d in valid_digits)

# Remainer == 2
elif digit_sum % 3 == 2:

if (len(remainder_1) > 1) and (len(remainder_2) > 0):

remainder_1 = sorted(remainder_1)
if min(remainder_2) <= sum(remainder_1[:2]):

idx = remainder_2.index(min(remainder_2))

valid_digits += remainder_0
valid_digits += remainder_1
valid_digits += remainder_2[:idx]
valid_digits += remainder_2[idx+1:]

else:

valid_digits += remainder_0
valid_digits += remainder_1[2:]
valid_digits += remainder_2

elif len(remainder_2) > 0:

idx = remainder_2.index(min(remainder_2))

valid_digits += remainder_0
valid_digits += remainder_1
valid_digits += remainder_2[:idx]
valid_digits += remainder_2[idx+1:]

elif len(remainder_1) > 1:

remainder_1 = sorted(remainder_1)

valid_digits += remainder_0
valid_digits += remainder_1[2:]
valid_digits += remainder_2

else:

valid_digits += remainder_0

assert sum(valid_digits) % 3 == 0
valid_digits = sorted(valid_digits)[::-1]

if len(valid_digits) == 0:
return ""

elif valid_digits[0] == 0:
return "0"

else:
return "".join(str(d) for d in valid_digits)```