Maximize sum of array by repeatedly removing an element from pairs whose concatenation is a multiple of 3

Maximize sum of array by repeatedly removing an element from pairs whose concatenation is a multiple of 3

Given an array arr[] consisting of N positive integers, the task is to find the maximum possible sum of the remaining array elements after repeatedly removing the any of the two elements whose concatenation is a multiple of 3.

Examples:

Input: arr[] = {23, 12, 43, 3, 56}
Output: 91
Explanation:
Initially the array is {23, 12, 43, 3, 56}. Following removal of array elements are performed:

• Pair {23, 43}: Concatenation = 2343, which is divisible by 3. Now, removing 43 modifies the array to {23, 12, 3, 56}.
• Pair {12, 3}: Concatenation = 123, which is divisible by 3. Now, removing 3 modifies the array to {23, 12, 56}.

After the above operations, sum of the array elements = 12 + 56 + 23 = 91.

Input: arr[] = {324, 32, 53, 67, 330}
Output: 415

Approach: The given problem can be solved by using the fact that the remainder of a number, when divided by 3, is equal to the remainder of the sum of its digits when divided by 3. Follow the steps below to solve the problem:

• Initialize three variables, say maxRem0, maxRem1, and maxRem2, to store the element having remainder as 0, 1, and 2 respectively.
• Traverse the given array arr[] and perform the following steps:
  • Initialize a variable, digitSum to store the digit sum.
  • If digitSum % 3 == 0, then update the value of maxRem0 as max(maxRem0, arr[i]).
  • Otherwise, if the remainder is 1 or 2, then
• After completing the above steps, print the sum of maxRem0 and the maximum value of maxRem1 and maxRem2 as the result.

Below is the implementation of the above approach:

Python3

def getSum(n):   ans = 0   for i in str(n):     ans += int(i)          return ans    def getMax(arr):                        maxRem0 = 0            rem1 = 0     rem2 = 0        for i in arr:                           digitSum = getSum(i)                             if digitSum % 3 == 0:             maxRem0 = max(maxRem0, i)                                 elif digitSum % 3 == 1:             rem1 += i                                             else:             rem2 += i                              print( maxRem0 + max(rem1, rem2))       arr = [ 23, 12, 43, 3, 56 ] getMax(arr)

Output:

91

Time Complexity: O(N)
Auxiliary Space: O(1)

Attention reader! Don’t stop learning now. Get hold of all the important mathematical concepts for competitive programming with the Essential Maths for CP Course at a student-friendly price. To complete your preparation from learning a language to DS Algo and many more,  please refer Complete Interview Preparation Course.

Let's block ads! (Why?)

Original page link

Best Cool Tech Gadgets

Top favorite technology gadgets