Best solutions for Microsoft interview tasks. Max Sum of Numbers With Same Digit Sum

Description:

Microsoft | OA 2020 | Max Sum of Numbers With Same Digit Sum - LeetCode Discuss

Solution:

In this task we need to do following things:

1. We need to write a function which returns sum of digits for a given number.
2. We need to make a hash map where the key is the sum of digits of the given number and the value is this number.
3. Then we will take each given number and put sum of it’s digits and the number itself into the hash map
4. If the hash map contains this sum we check if sum of our number and number from the map is bigger than maximum encountered sum of numbers.
5. If yes we save this sum as the maximum sum and save in the hash map given number if it is bigger than the number from the map.

// this function returns sum of digits of a given number
int dsum(int a) {
    int s = 0;
    for (; a > 0; a /= 10) {
        s += a % 10;
    }
    return s;
}
int solution(const vector<int> & v) {
    using sum_t = int;
    using number_t = int;
    unordered_map<sum_t, number_t> m;
    // Maximum sum of given numbers
    int max_sum = 0;
    for (auto i : v) {
        int s = dsum(i);
        // If we have no such sum of digits in the map 
        if (!m.count(s)) {
            // add this sum to the map as a key and the number 
            // as a value 
            m[s] = i;
        }
        else {
            // if we have the sum of digits in the map
            // if sum of current number and number from 
            // the map with the same sum of digits are bigger than
            // maximum encountered sum then update the maximum sum
            max_sum = max(max_sum, m[s] + i);
            // Save current number as value for current sum 
            // of digits if it is bigger than number from the map
            m[s] = max(i, m[s]);
        }
    }
    // if the are no numbers with equal sum return -1
    return max_sum ? max_sum : -1;
}

Repository with the full project you can find here: https://github.com/jolly-fellow/microsoft/tree/master/numbers_with_equal_digit_sum

Return to the table of contents.