Maximum pair sum such that their digit sum are equal and divisible by K

By Ann Roberts On Nov 1, 2022

View Discussion

Improve Article

Save Article

Like Article

View Discussion

Improve Article

Save Article

Like Article

Given a positive integer array arr[] of size N (1 ≤ N ≤ 10⁵) and a positive integer K, the task is to find the maximum value of arr[i] + arr[j] by choosing two indices i and j, such that i != j, and the sum of digits of the element at arr[i] should be equal to arr[j] and are divisible by K.

Examples:

Input: arr = [18, 43, 36, 13, 7]
Output: 54
Explanation:The pairs (i, j) that satisfy the conditions are:
Index (0, 2), both numbers have a sum of digits equal to 9, and their sum is 18 + 36 = 54.
Index (1, 4), both numbers have a sum of digits equal to 7, and their sum is 43 + 7 = 50.
So the maximum sum that we can obtain is 54.

Input: arr = [10, 12, 19, 14]
Output: -1
Explanation: There are no two numbers that satisfy the conditions, so we return -1

An approach using Hashing:

Use map to store all elements having same digit sum in sorted order and then again iterate over the map for each different digit sum which are divisible by K and maximize result with two greatest elements.

Follow the steps below to implement the above idea:

Initialize a map for mapping elements that have the same digit sum and Keep the value of the map in sorted order.
Iterating on the given array
- Initialize a variable sum for calculating the sum of digits
- Calculate the sum of the digit of element arr[i]
- Insert an element into the map having the sum of digits in “sum”
- Initialize a variable result for storing the maximum sum possible
Iterate over the map
- Check if the digit sum is divisible by K and the value of the key is greater than 1 (it’ll ensure that there are at least two elements whose digit sum is divisible by K).
  - Maximize the result by summation of the last two elements that are stored in the map
Return the result

Below is the implementation of the above approach.

C++

#include <bits/stdc++.h>

using namespace std;

int maximumSum(vector<int>& arr, int K)

{

unordered_map<int, multiset<int> > unmap;

for (int i = 0; i < arr.size(); i++) {

int sum = 0, t = arr[i];

while (t) {

sum += t % 10;

t /= 10;

}

unmap[sum].insert(arr[i]);

}

int result = -1;

for (auto it : unmap) {

if (it.first % K == 0 && it.second.size() > 1) {

auto i = it.second.rbegin();

result = max(result, *i + *(++i));

}

return result;

}

int main()

{

vector<int> arr = { 18, 43, 36, 13, 7 };

int K = 3;

cout << maximumSum(arr, K);

return 0;

}

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

View Discussion

Improve Article

Save Article

Like Article

View Discussion

Improve Article

Save Article

Like Article

Examples:

Input: arr = [18, 43, 36, 13, 7]
Output: 54
Explanation:The pairs (i, j) that satisfy the conditions are:
Index (0, 2), both numbers have a sum of digits equal to 9, and their sum is 18 + 36 = 54.
Index (1, 4), both numbers have a sum of digits equal to 7, and their sum is 43 + 7 = 50.
So the maximum sum that we can obtain is 54.

Input: arr = [10, 12, 19, 14]
Output: -1
Explanation: There are no two numbers that satisfy the conditions, so we return -1

An approach using Hashing:

Use map to store all elements having same digit sum in sorted order and then again iterate over the map for each different digit sum which are divisible by K and maximize result with two greatest elements.

Follow the steps below to implement the above idea:

Initialize a map for mapping elements that have the same digit sum and Keep the value of the map in sorted order.
Iterating on the given array
- Initialize a variable sum for calculating the sum of digits
- Calculate the sum of the digit of element arr[i]
- Insert an element into the map having the sum of digits in “sum”
- Initialize a variable result for storing the maximum sum possible
Iterate over the map
- Check if the digit sum is divisible by K and the value of the key is greater than 1 (it’ll ensure that there are at least two elements whose digit sum is divisible by K).
  - Maximize the result by summation of the last two elements that are stored in the map
Return the result

Below is the implementation of the above approach.

C++

#include <bits/stdc++.h>

using namespace std;

int maximumSum(vector<int>& arr, int K)

{

unordered_map<int, multiset<int> > unmap;

for (int i = 0; i < arr.size(); i++) {

int sum = 0, t = arr[i];

while (t) {

sum += t % 10;

t /= 10;

}

unmap[sum].insert(arr[i]);

}

int result = -1;

for (auto it : unmap) {

if (it.first % K == 0 && it.second.size() > 1) {

auto i = it.second.rbegin();

result = max(result, *i + *(++i));

}

return result;

}

int main()

{

vector<int> arr = { 18, 43, 36, 13, 7 };

int K = 3;

cout << maximumSum(arr, K);

return 0;

}

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

Read original article here

Denial of responsibility! Techno Blender is an automatic aggregator of the all world’s media. In each content, the hyperlink to the primary source is specified. All trademarks belong to their rightful owners, all materials to their authors. If you are the owner of the content and do not want us to publish your materials, please contact us by email – [email protected]. The content will be deleted within 24 hours.