Given an integer array of digits, return the largest multiple of three that can be formed by concatenating some of the given digits in any order.
Since the answer may not fit in an integer data type, return the answer as a string.
If there is no answer return an empty string.
 
Example 1:
Input: digits = [8,1,9]
Output: "981"

Example 2:
Input: digits = [8,6,7,1,0]
Output: "8760"

Example 3:
Input: digits = [1]
Output: ""

Example 4:
Input: digits = [0,0,0,0,0,0]
Output: "0"

 
Constraints:

1 <= digits.length <= 10^4
0 <= digits[i] <= 9
The returning answer must not contain unnecessary leading zeros.

Source: leetcode | Difficulty: MEDIUM
Tags: Dynamic programming

Data structures

Greedy algorithms

Starter code: class Solution:
    def largestMultipleOfThree(self, digits: List[int]) -> str:
        

Solutions:
class Solution:

	def largestMultipleOfThree(self, digits: List[int]) -> str:
		counts = Counter(digits)
		m = sum(digits) % 3
		if m:
			if counts[m] + counts[m + 3] + counts[m + 6]:
				counts[min([m + i for i in [0, 3, 6] if counts[m + i]])] -= 1
			else:
				counts[min([i - m for i in [3, 6, 9] if counts[i - m]])] -= 1
				counts[min([i - m for i in [3, 6, 9] if counts[i - m]])] -= 1
		ans = ''
		for i in range(9, -1, -1):
			if not ans and (not counts[i]):
				continue
			ans += str(i) * counts[i]
		if ans:
			return ans.lstrip('0') or '0'
		return ''


class Solution:

	def largestMultipleOfThree(self, digits: List[int]) -> str:
		(heaps, total) = ([[], [], []], 0)
		for digit in digits:
			total += digit
			heapq.heappush(heaps[digit % 3], str(digit))
		if (r := (total % 3)):
			if heaps[r]:
				heapq.heappop(heaps[r])
			elif len(heaps[-r]) > 1:
				heapq.heappop(heaps[-r])
				heapq.heappop(heaps[-r])
		if any(heaps):
			return str(int(''.join(sorted(sum(heaps, []), reverse=True))))
		return ''


class Solution:

	def largestMultipleOfThree(self, d: List[int]) -> str:
		d1 = sorted([i for i in d if i % 3 == 1])
		d2 = sorted([i for i in d if i % 3 == 2])
		d3 = [i for i in d if i % 3 == 0]
		if sum(d) % 3 == 1:
			if len(d1) != 0:
				res = d1[1:] + d2 + d3
			else:
				res = d2[2:] + d3
		elif sum(d) % 3 == 2:
			if len(d2) != 0:
				res = d1 + d2[1:] + d3
			else:
				res = d1[2:] + d3
		else:
			res = d
		res.sort(reverse=True)
		if not res:
			return ''
		return str(int(''.join([str(i) for i in res])))


class Solution:

	def largestMultipleOfThree(self, digits: List[int]) -> str:
		mod_gap = sum(digits) % 3
		if mod_gap == 0:
			answer = ''.join([str(i) for i in sorted(digits, reverse=True)])
		mult3 = [i for i in digits if i % 3 == 0]
		non3 = [i for i in digits if i % 3 != 0]
		non3 = sorted(non3, reverse=True)
		if mod_gap == 1:
			last_odd_idx = [i for i in range(len(non3)) if non3[i] & 1]
			if len(last_odd_idx) > 0:
				last_odd_idx = last_odd_idx[-1]
				non3 = non3[:last_odd_idx] + non3[last_odd_idx + 1:]
		elif mod_gap == 2:
			last_even_idx = [i for i in range(len(non3)) if non3[i] % 2 == 0]
			if len(last_even_idx) > 0:
				last_even_idx = last_even_idx[-1]
				non3 = non3[:last_even_idx] + non3[last_even_idx + 1:]
		if sum(non3) % 3 != 0:
			non3 = []
		answer = ''.join([str(int(i)) for i in sorted(mult3 + non3, reverse=True)])
		while answer.startswith('0') and len(answer) > 1:
			answer = answer[1:]
		return answer


class Solution:

	def largestMultipleOfThree(self, digits: List[int]) -> str:
		dp = [-1, -1, -1]
		for x in sorted(digits, reverse=True):
			r = x % 3
			r1 = 0
			for y in list(dp):
				if y == -1:
					dp[r] = max(dp[r], x)
				else:
					dp[(r1 + r) % 3] = max(dp[(r1 + r) % 3], 10 * y + x)
				r1 += 1
		if dp[0] == -1:
			return ''
		else:
			return str(dp[0])


class Solution:

	def largestMultipleOfThree(self, a: List[int]) -> str:
		(n, dp) = (len(a), [''] * 3)
		a.sort(reverse=True)
		for i in range(n):
			(d, dp1) = (a[i] % 3, [''] * 3)
			for j in range(3):
				k = (j - d) % 3
				dp1[j] = max([dp[k] + str(a[i]) if dp[k] or k == 0 else '', dp[j]], key=lambda x: (len(x), x))
				if len(dp1[j]) >= 2 and dp1[j][0] == '0':
					dp1[j] = dp1[j][1:]
			dp = dp1
		return dp[0]


class Solution:

	def largestMultipleOfThree(self, digits: List[int]) -> str:
		digits = collections.Counter(digits)
		final_ans_digits = {i: 0 for i in range(10)}
		for i in range(0, 10, 3):
			final_ans_digits[i] = digits[i]
		left_numbers = list()
		for i in [1, 2, 4, 5, 7, 8]:
			if digits[i] > 3:
				undefined = 3 + digits[i] % 3
				left_numbers += [i] * undefined
			else:
				left_numbers += [i] * digits[i]
		mod = sum(left_numbers) % 3
		if not mod:
			pass
		elif not (left_numbers[0] - mod) % 3:
			digits[left_numbers[0]] -= 1
		else:
			num1 = None
			for n in left_numbers:
				if not (n - mod) % 3:
					num1 = n
					digits[n] -= 1
					break
			if num1 is None:
				num2 = None
				for i in range(1, len(left_numbers)):
					if not (left_numbers[i] + left_numbers[0] - mod) % 3:
						num2 = left_numbers[i]
						digits[left_numbers[0]] -= 1
						digits[num2] -= 1
				if num2 is None:
					return ''
		ans = ''.join((str(i) * digits[i] for i in range(9, -1, -1)))
		if not ans:
			return ''
		elif ans[0] == '0':
			return '0'
		else:
			return ans


import numpy as np

class Solution:

	def largestMultipleOfThree(self, digits: List[int]) -> str:
		mod_gap = sum(digits) % 3
		if mod_gap == 0:
			answer = ''.join([str(i) for i in sorted(digits, reverse=True)])
		digits = np.array(digits)
		cond = digits % 3 == 0
		mult3 = digits[cond]
		non3 = digits[~cond]
		non3 = sorted(non3, reverse=True)
		non3 = np.array(non3)
		if mod_gap == 1:
			last_odd_idx = np.ravel(np.argwhere(non3 & 1))
			if len(last_odd_idx) > 0:
				last_odd_idx = last_odd_idx[-1]
				non3 = list(non3[:last_odd_idx]) + list(non3[last_odd_idx + 1:])
		elif mod_gap == 2:
			last_even_idx = np.ravel(np.argwhere(non3 % 2 == 0))
			if len(last_even_idx) > 0:
				last_even_idx = last_even_idx[-1]
				non3 = list(non3[:last_even_idx]) + list(non3[last_even_idx + 1:])
		if sum(non3) % 3 != 0:
			non3 = []
		answer = ''.join([str(int(i)) for i in sorted(np.concatenate([mult3, non3]), reverse=True)])
		while answer.startswith('0') and len(answer) > 1:
			answer = answer[1:]
		return answer


class Solution:

	def largestMultipleOfThree(self, digits: List[int]) -> str:
		digits.sort(reverse=True)
		N = len(digits)
		dp = [[float('-inf')] * N for _ in range(3)]
		for n in range(N):
			for k in [0, 1, 2, 0]:
				if n == 0 or (dp[k][n - 1] == float('-inf') and dp[(k - digits[n]) % 3][n - 1] == float('-inf')):
					if digits[n] % 3 == k:
						dp[k][n] = digits[n]
				elif digits[n] % 3 == 0:
					dp[k][n] = dp[k][n - 1] * 10 + digits[n]
				else:
					dp[k][n] = max(dp[k][n - 1], dp[(k - digits[n]) % 3][n - 1] * 10 + digits[n])
		return str(dp[0][-1]) if dp[0][-1] != float('-inf') else ''


class Solution:

	def largestMultipleOfThree(self, digits: List[int]) -> str:
		state2nums = defaultdict(Counter)
		digits.sort(reverse=True)
		for num in digits:
			delta = num % 3
			nstate = defaultdict(Counter)
			for i in range(3):
				if sum((v for (k, v) in list(state2nums[i].items()))) == 0 and i != 0:
					continue
				target = (delta + i) % 3
				if sum((v for (k, v) in list(state2nums[target].items()))) < sum((v for (k, v) in list(state2nums[i].items()))) + 1:
					counter = Counter(state2nums[i])
					counter[num] += 1
					nstate[target] = counter
			for i in range(3):
				if i in nstate:
					state2nums[i] = nstate[i]
		print(state2nums)
		nums = sorted([k for (k, v) in list(state2nums[0].items()) for _ in range(v)], reverse=True)
		ret = ''.join(map(str, nums))
		return '0' if ret and ret[0] == '0' else ret


class Solution:

	def largestMultipleOfThree(self, digits: List[int]) -> str:
		n = len(digits)
		f = [0] * 10
		for x in digits:
			f[x] += 1
		M = defaultdict(int)

		def upper(d, m):
			if f[d] < m:
				return 0
			return (f[d] - m) // 3 * 3 + m

		def mx(d, mod):
			dm = d % 3
			if dm == 0:
				return 0 if mod != 0 else f[d]
			if dm == 1:
				return upper(d, mod)
			if dm == 2:
				return upper(d, (3 - mod) % 3)
		for i in range(10):
			for j in range(3):
				M[i, j] = mx(i, j)
		X = [0] * 10
		R = [0] * 10

		def findout(i, mod):
			if i < 0:
				if mod == 0:
					gt = False
					sx = sr = 0
					for i in range(10):
						sx += X[i]
						sr += R[i]
					if sx > sr:
						gt = True
					elif sx == sr:
						for i in reversed(list(range(10))):
							if X[i] > R[i]:
								gt = True
								break
							elif X[i] < R[i]:
								break
					if gt:
						for i in range(10):
							R[i] = X[i]
				return
			for j in range(3):
				if M[i, j] > 0:
					X[i] = M[i, j]
					findout(i - 1, (mod + j) % 3)
					X[i] = 0
			findout(i - 1, mod)
		findout(9, 0)
		ret = ''
		for i in reversed(list(range(10))):
			if R[i] > 0:
				ret += R[i] * str(i)
		if len(ret) > 0 and ret[0] == '0':
			ret = '0'
		return ret


class Solution:

	def largestMultipleOfThree(self, digits: List[int]) -> str:
		dp = [-1, -1, -1]
		for x in sorted(digits)[::-1]:
			for a in dp[:] + [0]:
				y = a * 10 + x
				dp[y % 3] = max(dp[y % 3], y)
		return str(dp[0]) if dp[0] >= 0 else ''


class Solution:

	def largestMultipleOfThree(self, digits: List[int]) -> str:
		vals = {0: 0, 1: 0, 2: 0, 3: 0, 4: 0, 5: 0, 6: 0, 7: 0, 8: 0, 9: 0}
		total = 0
		res = []
		for digit in digits:
			vals[digit] += 1
			total += int(digit)
		if total % 3 == 0:
			temp = 0
			for i in range(9, 0, -1):
				temp += vals[i]
			if temp == 0:
				return '0'
			for i in range(9, -1, -1):
				for _ in range(vals[i]):
					res.append(str(i))
			return ''.join(res)
		if total % 3 == 1:
			for i in range(10):
				if i % 3 == 1 and vals[i] > 0:
					vals[i] -= 1
					for i in range(9, -1, -1):
						for _ in range(vals[i]):
							res.append(str(i))
					return ''.join(res)
			count = 0
			i = 0
			while i < 10:
				if count == 2:
					for i in range(9, -1, -1):
						for _ in range(vals[i]):
							res.append(str(i))
					return ''.join(res)
				elif i % 3 == 2 and vals[i] > 0:
					vals[i] -= 1
					count += 1
				else:
					i += 1
		else:
			for i in range(10):
				if i % 3 == 2 and vals[i] > 0:
					vals[i] -= 1
					for i in range(9, -1, -1):
						for _ in range(vals[i]):
							res.append(str(i))
					return ''.join(res)
			count = 0
			i = 0
			while i < 10:
				if count == 2:
					for i in range(9, -1, -1):
						for _ in range(vals[i]):
							res.append(str(i))
					return ''.join(res)
				elif i % 3 == 1 and vals[i] > 0:
					vals[i] -= 1
					count += 1
				else:
					i += 1
		return ''.join(res)


class Solution:

	def largestMultipleOfThree(self, digits: List[int]) -> str:
		r_to_nums = {i: list() for i in range(3)}
		for x in digits:
			r = x % 3
			r_to_nums[r].append(x)
		for i in range(3):
			r_to_nums[i].sort()
		counter = collections.Counter()
		for x in digits:
			counter[str(x)] += 1
		r = sum(digits) % 3
		if r == 1:
			if r_to_nums[1]:
				y = str(r_to_nums[1][0])
				counter[y] -= 1
			elif len(r_to_nums[2]) >= 2:
				y = str(r_to_nums[2][0])
				counter[y] -= 1
				y = str(r_to_nums[2][1])
				counter[y] -= 1
			else:
				return ''
		elif r == 2:
			if r_to_nums[2]:
				y = str(r_to_nums[2][0])
				counter[y] -= 1
			elif len(r_to_nums[1]) >= 2:
				y = str(r_to_nums[1][0])
				counter[y] -= 1
				y = str(r_to_nums[1][1])
				counter[y] -= 1
			else:
				return ''
		res = ''
		for x in sorted(counter, reverse=True):
			cnt = counter[x]
			res += x * cnt
		if not res:
			return res
		return str(int(res))


class Solution:

	def largestMultipleOfThree(self, digits: List[int]) -> str:
		dic = defaultdict(list)
		for d in digits:
			dic[d % 3].append(d)
		arr = []
		n1 = len(dic[1])
		n2 = len(dic[2])
		arr += dic[0]
		if n1 % 3 == n2 % 3 == 0 or n1 == n2:
			arr += dic[1] + dic[2]
		else:
			dic[1].sort(reverse=1)
			dic[2].sort(reverse=1)
			l1 = l2 = 0
			if n1 % 3 == 2 and n2 == 3:
				while n2 > 3:
					l2 += 3
					n2 -= 3
				l1 += n1 // 3 * 3
				l1 += 2
				l2 += 2
			elif n2 % 3 == 2 and n1 == 3:
				while n1 > 3:
					l1 += 3
					n1 -= 3
				l2 += n2 // 3 * 3
				l2 += 2
				l1 += 2
			else:
				if n1 > 2:
					l1 += n1 // 3 * 3
					n1 -= n1 // 3 * 3
				if n2 > 2:
					l2 += n2 // 3 * 3
					n2 -= n2 // 3 * 3
				if n1 != 0 and n2 != 0:
					min1 = min(n1, n2)
					l1 += min1
					l2 += min1
			arr += dic[1][:l1] + dic[2][:l2]
		arr.sort(reverse=1)
		if arr and arr[0] == 0:
			return '0'
		return ''.join((str(i) for i in arr))