Maximum Sum – Equal Digits Sum

Find the maximum sum of any two integers from a list whose digit sums are equal, or return -1 if no such pair exists.

Understand the Problem

Problem Statement

Given N integers, find the maximum possible sum of any two integers whose digits add up to the same total. If no such pair exists, print -1.

Constraints

1 ≤ N ≤ 100
1 ≤ Each integer value ≤ 10^8
Integers can be positive
Output should be the maximum sum possible, or -1 if no valid pair exists

Examples

Example 1

Input

4
15 81 24 36

Output

Explanation

Digit sums: 15→6, 81→9, 24→6, 36→9. Groups: {6: [15, 24], 9: [81, 36]}. Maximum sums: 15+24=39, 81+36=117. The answer is 117.

Example 2

Input

7
20 3 13 18 9 21 22

Output

Explanation

Digit sums: 20→2, 3→3, 13→4, 18→9, 9→9, 21→3, 22→4. Valid groups: {3: [3, 21], 4: [13, 22], 9: [18, 9]}. Maximum sums: 3+21=24, 13+22=35, 18+9=27. The answer is 35.

Example 3

Input

5
156 12 49 24 99

Output

-1

Explanation

Digit sums: 156→12, 12→3, 49→13, 24→6, 99→18. All digit sums are unique, so no valid pairs exist. The answer is -1.

Solution

#include <stdio.h>
#include <stdlib.h>

int digitSum(int n) {
    int sum = 0;
    while (n > 0) {
        sum += n % 10;
        n /= 10;
    }
    return sum;
}

int compare(const void *a, const void *b) {
    return (*(int*)b - *(int*)a);
}

int main() {
    int n;
    scanf("%d", &n);
    
    int numbers[100];
    int digitSums[100];
    
    for (int i = 0; i < n; i++) {
        scanf("%d", &numbers[i]);
        digitSums[i] = digitSum(numbers[i]);
    }
    
    int maxSum = -1;
    
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (digitSums[i] == digitSums[j]) {
                int currentSum = numbers[i] + numbers[j];
                if (currentSum > maxSum) {
                    maxSum = currentSum;
                }
            }
        }
    }
    
    printf("%d\n", maxSum);
    return 0;
}

Time:O(N²) - due to nested loops checking all pairs

Space:O(N) - for storing the numbers and their digit sums

Approach:

This C solution:

Defines a digitSum function to calculate the sum of digits for any number.
Reads all numbers and stores their digit sums in parallel arrays.
Uses nested loops to check all pairs of numbers.
When two numbers have the same digit sum, it calculates their sum and updates the maximum if applicable.
Finally prints the maximum sum found, or -1 if no valid pairs exist (maxSum remains -1).

Visual Explanation

Loading diagram...

All Problems