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 = [0]*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 = [0]*2 rem_2[0] = -1; rem_2[1] = -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[0] == -1: rem_2[0] = i # If second occurrence elif rem_2[1] == -1: rem_2[1] = i if rem_2[0] != -1 and rem_2[1] != -1: removeAndPrintResult(arr, n, rem_2[0], rem_2[1]) 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 = [0]*2 rem_1[0] = -1; rem_1[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[0] == -1: rem_1[0] = i # If second occurrence elif rem_1[1] == -1: rem_1[1] = i if rem_1[0] != -1 and rem_1[1] != -1: removeAndPrintResult(arr, n, rem_1[0], rem_1[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
Also read: Fetch top 10 starred repositories of user on GitHub using Python
Leave a Reply