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 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:
C++
// C++ approach for the above approach#include <bits/stdc++.h>using namespace std;// Function to calculate sum// of digits of an integerint getSum(int n){ int ans = 0; // char[] arr = (String.valueOf(n)).toCharArray(); string arr = to_string(n); for(int i = 0; i < arr.length(); i++) { ans += int(arr[i]); } return ans;}// Function to calculate maximum sum// of array after removing pairs whose// concatenation is divisible by 3void getMax(int arr[], int n){ // Stores the sum of // digits of array element int maxRem0 = 0; int rem1 = 0; int rem2 = 0; for(int i = 0; i < n; i++) { // Find the sum of digits int digitSum = getSum(arr[i]); // If i is divisible by 3 if (digitSum % 3 == 0) maxRem0 = max(maxRem0, arr[i]); // Otherwise, if i modulo 3 is 1 else if (digitSum % 3 == 1) rem1 += arr[i]; // Otherwise, if i modulo 3 is 2 else rem2 += arr[i]; } // Return the resultant // sum of array elements cout << (maxRem0 + max(rem1, rem2));}// Driver Codeint main(){ int arr[] = { 23, 12, 43, 3, 56 }; int n = sizeof(arr) / sizeof(arr[0]); getMax(arr, n);}// This code is contributed by ukasp |
Java
// Java approach for the above approachclass GFG{// Function to calculate sum// of digits of an integerstatic int getSum(int n){ int ans = 0; char[] arr = (String.valueOf(n)).toCharArray(); for(char ch : arr) { ans += Character.getNumericValue(ch); } return ans;}// Function to calculate maximum sum// of array after removing pairs whose// concatenation is divisible by 3static void getMax(int[] arr){ // Stores the sum of // digits of array element int maxRem0 = 0; int rem1 = 0; int rem2 = 0; for(int i:arr) { // Find the sum of digits int digitSum = getSum(i); // If i is divisible by 3 if (digitSum % 3 == 0) maxRem0 = Math.max(maxRem0, i); // Otherwise, if i modulo 3 is 1 else if (digitSum % 3 == 1) rem1 += i; // Otherwise, if i modulo 3 is 2 else rem2 += i; } // Return the resultant // sum of array elements System.out.print(maxRem0 + Math.max(rem1, rem2));}// Driver Codepublic static void main(String[] args){ int[] arr = { 23, 12, 43, 3, 56 }; getMax(arr);}}// This code is contributed by abhinavjain194 |
Python3
# Python3 program for the above approach# Function to calculate sum# of digits of an integer def getSum(n): ans = 0 for i in str(n): ans += int(i) return ans# Function to calculate maximum sum# of array after removing pairs whose# concatenation is divisible by 3def getMax(arr): # Stores the sum of # digits of array element maxRem0 = 0 rem1 = 0 rem2 = 0 for i in arr: # Find the sum of digits digitSum = getSum(i) # If i is divisible by 3 if digitSum % 3 == 0: maxRem0 = max(maxRem0, i) # Otherwise, if i modulo 3 is 1 elif digitSum % 3 == 1: rem1 += i # Otherwise, if i modulo 3 is 2 else: rem2 += i # Return the resultant # sum of array elements print( maxRem0 + max(rem1, rem2))# Driver Code# Given arrayarr = [ 23, 12, 43, 3, 56 ]getMax(arr) |
C#
// C# program for the above approachusing System;class GFG{ // Function to calculate sum// of digits of an integerstatic int getSum(int n){ int ans = 0; string str = n.ToString(); Char[] arr = str.ToCharArray(); foreach(Char ch in arr) { ans += (int)Char.GetNumericValue(ch); } return ans;} // Function to calculate maximum sum// of array after removing pairs whose// concatenation is divisible by 3static void getMax(int[] arr){ // Stores the sum of // digits of array element int maxRem0 = 0; int rem1 = 0; int rem2 = 0; foreach(int i in arr) { // Find the sum of digits int digitSum = getSum(i); // If i is divisible by 3 if (digitSum % 3 == 0) maxRem0 = Math.Max(maxRem0, i); // Otherwise, if i modulo 3 is 1 else if (digitSum % 3 == 1) rem1 += i; // Otherwise, if i modulo 3 is 2 else rem2 += i; } // Return the resultant // sum of array elements Console.WriteLine(maxRem0 + Math.Max(rem1, rem2));}// Driver Codestatic void Main(){ int[] arr = { 23, 12, 43, 3, 56 }; getMax(arr);}}// This code is contributed by souravghosh0416. |
Javascript
<script> // Javascript program for the // above approach // Function to calculate sum // of digits of an integer function getSum(n) { let ans = 0; let arr = n.toString(); for (let i = 0; i < arr.length; i++) { ans += arr[i]; } return ans; } // Function to calculate maximum sum // of array after removing pairs whose // concatenation is divisible by 3 function getMax(arr, n) { // Stores the sum of // digits of array element let maxRem0 = 0; let rem1 = 0; let rem2 = 0; for (let i = 0; i < n; i++) { // Find the sum of digits let digitSum = getSum(arr[i]); // If i is divisible by 3 if (digitSum % 3 == 0) maxRem0 = Math.max(maxRem0, arr[i]); // Otherwise, if i modulo 3 is 1 else if (digitSum % 3 == 1) rem1 += arr[i]; // Otherwise, if i modulo 3 is 2 else rem2 += arr[i]; } // Return the resultant // sum of array elements document.write(maxRem0 + Math.max(rem1, rem2)) } // Driver Code let arr = [23, 12, 43, 3, 56]; let n = arr.length; getMax(arr, n); // This code is contributed by Hritik </script> |
Output:
91
Time Complexity: O(n * k), where n is the size of the array and k is the maximum number of digits in an array element.
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
