This article describes the question from Day 14 of the 30 Days of Code competition hosted by Geeks for Geeks.

Question

Geek Land has a population of N people and each person's ability to rule the town is measured by a numeric value arr[i]. The two people that can together rule Geek Land must be compatible with each other i.e., the sum of digits of their ability arr[i] must be equal. Their combined ability should be maximum amongst all the possible pairs of people. Find the combined ability of the Ruling Pair.

Example 1:

Input: N = 5 arr[] = {55, 23, 32, 46, 88} Output: 101 Explanation: All possible pairs that are compatible with each other are- (23, 32) with digit sum 5 and (55, 46) with digit sum 10. Out of these the maximum combined ability pair is (55, 46) i.e. 55 + 46 = 101

Example 2:

Input: N = 4 arr[] = {18, 19, 23, 15} Output: -1 Explanation: No two people are compatible with each other.

Your Task:
You don't need to read input or print anything. Complete the function RulingPair​() which takes the array arr[] and size of array N as input parameters and returns the answer. If No two people are compatible with each other then return -1.

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

Constraints: 1 ≤ N ≤ 105 1 ≤ arr[i] ≤ 109

Solution

Here is the solution below in Python.

class Solution:
    def digitSum(self, n):
        s = 0
        while n:
            s += n % 10
            n = n // 10
        return s

    def RulingPair(self, arr, n): 
        m = -1
        h = {}
        for a in arr:
            t = a 
            s = self.digitSum(a)
            if s in h:
                m = max(m, a + h[s])
                if t > h[s]:
                    h[s] = t
            else:
                h[s] = a
        return m

Firstly, we create a helper method digitSum(). This calculates the sum of the digits in a number. For example, if n were 55, its digit sum would be 5 + 5 = 10. The while loop in this method accumulates the sum from the left, starting in the ones. Then we divide by 10, discarding any remainder with the // operation, getting rid of the value that was previously in the one's column. No were are adding the tens value to our sum. So on and so forth, this process is repeated until all digits are expended.

We are only considering pairs whose digit sums are equal. To avoid backtracking, we store the existing digit sums in a dictionary h. We keep track of the current maximum combined ability m. To check if sums are equal, we see if that sum already exists in our dictionary. If so, we perform a maximum operation, to check if it is the largest pair so far. We check to see if the current number is larger than the previous which had that sum. If so, we replace the value that sum was the key for, with our current number. Since this is larger, it will form a greater combined pair than its predecessor.

If that sum does not exist, we simply add it to our map. So that later pairs may check if they are equal. Finally, we return our maximum pair m, after we have iterated over each item in the array. This algorithm calculates the maximum sum pair in one pass, or O(N). If no two abilities have the same digit sum, our dictionary will be empty, so the maximum will not be updated. Therefore it will return -1, with no possible ruling pairs.