Given a positive integer array arr[] of size N (1 ? N ? 105) 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
- 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).
- Return the result
Below is the implementation of the above approach.
C++
// C++ code to implement the approach#include <bits/stdc++.h>using namespace std;// Function to find the maximum pair sumint maximumSum(vector<int>& arr, int K){ // Initialize a map for mapping elements // that have same digit sum. Keep // value of map in sorted order. unordered_map<int, multiset<int> > unmap; // Iterating on given array for (int i = 0; i < arr.size(); i++) { // Initialize a variable sum for // calculating the sum of digits int sum = 0, t = arr[i]; // Calculate the sum of digit of // element arr[i] while (t) { sum += t % 10; t /= 10; } // Insert element into map having // sum of digit in "sum" unmap[sum].insert(arr[i]); } // Initialize a variable result for // storing the maximum sum possible int result = -1; // Iterate over the map for (auto it : unmap) { if (it.first % K == 0 && it.second.size() > 1) { auto i = it.second.rbegin(); // Maximize the result by // summation of last two // elements that are stored // in map result = max(result, *i + *(++i)); } } // Return the result return result;}// Driver codeint main(){ vector<int> arr = { 18, 43, 36, 13, 7 }; int K = 3; // Function Call cout << maximumSum(arr, K); return 0;} |
Java
// JAVA code to implement the approachimport java.util.*;public class Main { // Function to find the maximum pair sum static int maximumSum(int[] arr, int K) { // Initialize a map for mapping elements // that have same digit sum. Keep // value of map in sorted order. Map<Integer, List<Integer> > unmap = new HashMap<Integer, List<Integer> >(); // Iterating on given array for (int i = 0; i < arr.length; i++) { // Initialize a variable sum for // calculating the sum of digits int sum = 0, t = arr[i]; // Calculate the sum of digit of // element arr[i] while (t != 0) { sum += t % 10; t /= 10; } // Insert element into map having // sum of digit in "sum" if (unmap.containsKey(sum)) { List<Integer> list = unmap.get(sum); list.add(arr[i]); unmap.put(sum, list); } else { List<Integer> list = new ArrayList<>(); list.add(arr[i]); unmap.put(sum, list); } } // Initialize a variable result for // storing the maximum sum possible int result = -1; // Iterate over the map for (int key : unmap.keySet()) { List<Integer> list = unmap.get(key); Collections.sort(list); int x = list.size(); if (key % K == 0 && x > 1) { // Maximize the result by // summation of last two // elements that are stored // in map result = Math.max(result, list.get(x - 1) + list.get(x - 2)); } } // // Return the result return result; } public static void main(String[] args) { int[] arr = { 18, 43, 36, 13, 7 }; int K = 3; // Function Call System.out.println(maximumSum(arr, K)); }}// This code is contributed by garg28harsh. |
C#
using System;using System.Collections.Generic;namespace MaximumSum{ class MainClass { // Function to find the maximum pair sum static int MaximumSum(int[] arr, int K) { // Initialize a dictionary for mapping elements // that have same digit sum. Keep // value of dictionary in sorted order. Dictionary<int, List<int>> unmap = new Dictionary<int, List<int>>(); // Iterating on given array for (int i = 0; i < arr.Length; i++) { // Initialize a variable sum for // calculating the sum of digits int sum = 0, t = arr[i]; // Calculate the sum of digit of // element arr[i] while (t != 0) { sum += t % 10; t /= 10; } // Insert element into dictionary having // sum of digit in "sum" if (unmap.ContainsKey(sum)) { List<int> list = unmap[sum]; list.Add(arr[i]); unmap[sum] = list; } else { List<int> list = new List<int>(); list.Add(arr[i]); unmap[sum] = list; } } // Initialize a variable result for // storing the maximum sum possible int result = -1; // Iterate over the dictionary foreach (var key in unmap.Keys) { List<int> list = unmap[key]; list.Sort(); int x = list.Count; if (key % K == 0 && x > 1) { // Maximize the result by // summation of last two // elements that are stored // in dictionary result = Math.Max(result, list[x - 1] + list[x - 2]); } } // Return the result return result; } public static void Main(string[] args) { int[] arr = { 18, 43, 36, 13, 7 }; int K = 3; // Function Call Console.WriteLine(MaximumSum(arr, K)); } }} |
Javascript
// JavaScript code to implement the approach// Function to find the maximum pair sumfunction maximumSum(arr, K){ // Initialize a map for mapping elements // that have same digit sum. Keep // value of map in sorted order. let unmap = {}; // Iterating on given array for (let i = 0; i < arr.length; i++) { // Initialize a variable sum for // calculating the sum of digits let sum = 0, t = arr[i]; // Calculate the sum of digit of // element arr[i] while (t) { sum += t % 10; t /= 10; } // Insert element into map having // sum of digit in "sum" if(unmap.hasOwnProperty(sum)){ unmap[sum].push(arr[i]); } else { unmap[sum] = [arr[i]]; } } // Initialize a variable result for // storing the maximum sum possible let result = -1; // Iterate over the map for (let key of Object.keys(unmap)) { if (key % K == 0 && unmap[key].length > 1) { let lastIndex = unmap[key].length -1; // Maximize the result by // summation of last two // elements that are stored // in map result = Math.max(result, unmap[key][lastIndex] + unmap[key][lastIndex-1]); } } // Return the result return result;}// Driver codelet arr = [ 18, 43, 36, 13, 7 ];let K = 3;// Function Callconsole.log(maximumSum(arr, K));// This code is contributed by Kanishka Gupta |
Python3
# Function to find the maximum pair sumdef maximum_sum(arr, K): # Initialize a map for mapping elements # that have same digit sum. Keep # value of map in sorted order. unmap = {} # Iterating on given array for i in range(len(arr)): # Initialize a variable sum for # calculating the sum of digits sum = 0 t = arr[i] # Calculate the sum of digit of # element arr[i] while t: sum += t % 10 t //= 10 # Insert element into map having # sum of digit in "sum" if sum in unmap: unmap[sum].append(arr[i]) else: unmap[sum] = [arr[i]] # Initialize a variable result for # storing the maximum sum possible result = -1 # Iterate over the map for key in unmap: if key % K == 0 and len(unmap[key]) > 1: # Maximize the result by # summation of last two # elements that are stored # in map unmap[key].sort(reverse=True) result = max(result, unmap[key][0] + unmap[key][1]) # Return the result return result# Driver codearr = [18, 43, 36, 13, 7]K = 3# Function Callprint(maximum_sum(arr, K)) |
Output
54
Time Complexity: O(N)
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Share your thoughts in the comments
