# Calculate largest multiple of 3 in Python

In this article, you will learn to Calculate the largest multiple of 3 in Python.

### Problem: largest multiple of 3 in Python from the given digits

We have to find the largest multiple of 3 that can be formed from array elements(we have an array of positive integers).

For example, if we have an input list of {5,6,4}, the output will be “54”, and if the input list is {5,6,7,4,1}, the output will be “7641”.

#### Basic Approach-

Generate all the combinations of given digits and the maximum number that is divisible by 3 is the result.
But, it will have a time complexity of O(2^n).

#### Better Approach-

The sum of the digits of the multiple is divisible by 3.

453 is divisible by 3 and (4+5+3=12) is also divisible by 3.

```#Python program
MAX_SIZE = 10
def sortArray(arr, n):

count = *MAX_SIZE
for i in range(n):
count[arr[i]] += 1

index = 0
for i in range(MAX_SIZE):
while count[i] > 0:
arr[index] = i
index += 1
count[i] -= 1
def removePrintResult(arr, n, ind1, ind2=-1):
for i in range(n-1, -1, -1):
if i != ind1 and i != ind2:
print(arr[i], end="")

def largest3Multiple(arr, n):

# Sum of all array element
s = sum(arr)

# Sum is divisible by 3, no need to
# delete an element
if s % 3 == 0:
return True

# Sort array element in increasing order
sortArray(arr, n)

# Find reminder
remainder = s % 3

# If remainder is '1', we have to delete either
# one element of remainder '1' or two elements
# of remainder '2'
if remainder == 1:
rem_2 = *2
rem_2 = -1; rem_2 = -1

# Traverse array elements
for i in range(n):

# Store first element of remainder '1'
if arr[i] % 3 == 1:
removeAndPrintResult(arr, n, i)
return True

if arr[i] % 3 == 2:

# If this is first occurrence of remainder 2
if rem_2 == -1:
rem_2 = i

# If second occurrence
elif rem_2 == -1:
rem_2 = i

if rem_2 != -1 and rem_2 != -1:
removeAndPrintResult(arr, n, rem_2, rem_2)
return True

# If remainder is '2', we have to delete either
# one element of remainder '2' or two elements
# of remainder '1'
elif remainder == 2:
rem_1 = *2
rem_1 = -1; rem_1 = -1

# traverse array elements
for i in range(n):

# store first element of remainder '2'
if arr[i] % 3 == 2:
removeAndPrintResult(arr, n, i)
return True

if arr[i] % 3 == 1:

# If this is first occurrence of remainder 1
if rem_1 == -1:
rem_1 = i

# If second occurrence
elif rem_1 == -1:
rem_1 = i

if rem_1 != -1 and rem_1 != -1:
removeAndPrintResult(arr, n, rem_1, rem_1)
return True

print("Not possible")
return False

# Driver code
if __name__ == "__main__":

arr = [5,1,2,1]
n = len(arr)
largest3Multiple(arr, n)

```

Output:

`663`