Max Sum of a Pair With Equal Sum of Digits

class Solution {
public:
    int maxPairSum(vector<int>& arr) {
        int maxSum = -1;
        int sumMapping[82] = {};

        for (int num : arr) {
            int sumDigits = 0;
            for (int n = num; n; n /= 10) {
                sumDigits += n % 10;
            }

            if (sumMapping[sumDigits] > 0) {
                maxSum = max(maxSum, sumMapping[sumDigits] + num);
            }

            sumMapping[sumDigits] = max(sumMapping[sumDigits], num);
        }

        return maxSum;
    }
};

The provided C++ solution aims to find the maximum sum of a pair of numbers from an array where the sum of the digits of both numbers is equal. Here's a concise breakdown of how the problem is solved:

1. Initialize a variable maxSum to -1 to track the maximum sum of pairs found.
2. Use an array sumMapping sized 82 (since the maximum sum of digits possible for any number up to 999999999 is 81) to store the maximum number encountered with each specific digit sum.
3. Traverse each number in the input array:
   • Compute the sum of the digits of the current number.
   • If there's already a recorded number in sumMapping with the same digit sum, calculate the potential maximum sum with the current number and update maxSum.
   • Update sumMapping for the current digit sum to the maximum of the current number or the pre-stored number.

This method efficiently checks and updates potential pairs in a single pass through the array using the mapping of sum of digits to maximum values. The result, maxSum, gives the highest sum of any pair of numbers with equal digit sums, or -1 if no such pair exists.

class Solution {

    public int maxPairSumWithSameDigitSum(int[] arr) {
        int maxResult = -1;
        int[] sumToMaxValue = new int[82];

        for (int num : arr) {
            int sumDigits = 0;
            for (int n = num; n != 0; n /= 10) {
                sumDigits += n % 10;
            }

            if (sumToMaxValue[sumDigits] > 0) {
                maxResult = Math.max(maxResult, sumToMaxValue[sumDigits] + num);
            }

            sumToMaxValue[sumDigits] = Math.max(sumToMaxValue[sumDigits], num);
        }

        return maxResult;
    }
}

This Java solution is designed to find the maximum sum of a pair of elements in an array where each element in the pair has the same sum of digits. The method maxPairSumWithSameDigitSum utilizes an efficient approach:

• Initializes maxResult to -1 to handle cases where no valid pair exists.
• Sets up an array sumToMaxValue to store the maximum number encountered for each possible digit sum, which can range up to 81 (for 9999).

Steps in the Method:

1. Loop through each number in the input array:
2. Calculate the sum of digits for the current number using a nested loop which divides the number by 10 until the number becomes 0. The modulus operator (%) obtains the last digit during each iteration.
3. Update the maxResult if there is already a stored maximum value for the calculated digit sum in sumToMaxValue. This is achieved by checking if sumToMaxValue at the index of the current digit sum is greater than zero and then updating maxResult to the maximum of its current value or the sum of sumToMaxValue value and the current number.
4. Update the sumToMaxValue for the current digit sum to ensure it holds the largest number with that sum of digits.

Finally, the method returns maxResult, which is the maximum pair sum found where both numbers in the pair have the same digit sum, or -1 if no such pairs exist.

class Solution:
    def findMaxSum(self, arr):
        max_sum = -1
        sum_map = [0] * 82

        for num in arr:
            sum_digits = 0
            temp_num = num
            while temp_num:
                temp_num, last_digit = divmod(temp_num, 10)
                sum_digits += last_digit

            if sum_map[sum_digits] > 0:
                max_sum = max(max_sum, sum_map[sum_digits] + num)

            sum_map[sum_digits] = max(sum_map[sum_digits], num)

        return max_sum

The provided Python3 code focuses on solving the problem of finding the maximum sum of pairs in an array where the pairs have an equal sum of their digits. The function findMaxSum in the Solution class implements the logic needed to approach this problem.

• Initialize a variable max_sum to -1, which will store the result.
• Create a list sum_map of size 82 initialized with zeros.

The size 82 caters to the highest possible sum of digits for any number (considering the constraints usually set in competitive coding problems). The list sum_map is used to save the maximum number encountered with a specific sum of its digits.

• Iterate through each number in the input array arr.

• For each number, calculate the sum of its digits:

  • Initialize sum_digits to 0 to start summing the digits of num.
  • Utilize a while loop with divmod to extract and sum up the digits of num.

• After calculating sum_digits for the current num:

  • If sum_map[sum_digits] is greater than 0 (which means at least one number with this sum of digits was encountered before), update max_sum with the larger value between max_sum and the sum of sum_map[sum_digits] and the current number num.
  • Update the current index of sum_map to record the maximum number seen so far with the current sum of digits.

• Once the loop is over, return max_sum, which now contains the maximum sum of any pair of numbers in arr having the same sum of digits, or -1 if no such pairs exist. This method ensures a complete scan of the array, therefore, preserving efficiency and comprehensibility.