Maximizing product of elements with same Digit Product
Given a positive integer array arr[] of size N (1 ≤ N ≤ 10^5). The task is to find the maximum value of the product of two elements, arr[i] and arr[j], where i ≠ j, such that the product of their digits is equal and divisible by N. In case of no such solution, return -1.
Examples:
Input: arr = {15, 35, 7, 115, 53}
Output: 1855
Explanation: All pairs that satisfy the conditions are:
=> Index (1, 4), digits product of both elements are equal to 15, which are divisible by N and their product is 35 * 53 = 1855.
=> Index (0, 3), digits product of both elements are equal to 5, which are divisible by N and their product is 15* 115 = 1725
So the maximum product is 1855.Input: arr = {11, 12, 23, 14}.
Output: -1
Explanation: No such elements are there that satisfy the conditions, so return -1
Maximizing Product of Elements with Same Digit Product using Hashing:
To solve this problem, first use a map to store all elements with the same digit product in sorted order. Then, iterate over the map for each unique digit product that is divisible by N and maximize the result by selecting the two greatest elements with that digit product.
Step-by-step approach:
- Initialize a sorted map to group elements with the same digit product.
- Iterate over the array, calculating the digit product for each element and storing it in the map.
- Initialize a variable result for the maximum product.
- Iterate over the map, checking if the digit product is divisible by N and there are at least two elements.
- Maximize the result by product the two largest elements in the map.
- 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 Product int maximumProduct(vector< int >& arr) { int N = arr.size(); // Initilize a map for mapping elements // that have same digit product. Keep // value of map in sorted order. unordered_map< int , multiset< int > > unmap; // Iterating on given array for ( int i = 0; i < N; i++) { // Initilize a varaible product for // calculating the product of digits int product = 1, t = arr[i]; // Calculate the product of digit of // element arr[i] while (t) { product *= t % 10; t /= 10; } // Insert element into map having // product of digit in "product" unmap[product].insert(arr[i]); } // Initilize a varaible result for // storing the maximum product possible int result = -1; // Iterate over the map for ( auto it : unmap) { if (it.first % N == 0 && it.second.size() > 1) { auto i = it.second.rbegin(); // Maximize the result by // product of last two // elements that are stored // in map result = max(result, *i * *(++i)); } } // Return the result return result; } // Driver code int main() { vector< int > arr = {15, 35, 7, 115, 53}; // Function Call cout << maximumProduct(arr); return 0; } |
Java
// Java code to implement the approach import java.util.*; class GFG { // Function to find the maximum pair Product static int maximumProduct( int [] arr) { int N = arr.length; // Initilize a map for mapping elements // that have same digit product. Keep // value of map in sorted order. Map<Integer, List<Integer> > unmap = new HashMap<>(); // Iterating on given array for ( int i = 0 ; i < N; i++) { // Initilize a varaible product for // calculating the product of digits int product = 1 , t = arr[i]; // Calculate the product of digit of // element arr[i] while (t > 0 ) { product *= t % 10 ; t /= 10 ; } // Insert element into map having // product of digit in "product" List<Integer> temp = unmap.getOrDefault( product, new ArrayList<>()); temp.add(arr[i]); unmap.put(product, temp); } // Initilize a varaible result for // storing the maximum product possible int result = - 1 ; // Iterate over the map for (Map.Entry<Integer, List<Integer> > it : unmap.entrySet()) { if (it.getKey() % N == 0 && it.getValue().size() > 1 ) { List<Integer> temp = it.getValue(); int lastValue = temp.get(temp.size() - 1 ); int secondLast = temp.get(temp.size() - 2 ); // Maximize the result by // product of last two // elements that are stored // in map result = Math.max(result, lastValue * secondLast); } } // Return the result return result; } // Driver code public static void main(String[] args) { int [] arr = { 15 , 35 , 7 , 115 , 53 }; // Function Call System.out.println(maximumProduct(arr)); } } // This code is contributed by ragul21 |
Python3
# Python code to implement the approach # Function to find the maximum pair Product def maximumProduct(arr): N = len (arr) # Initilize a map for mapping elements # that have same digit product. Keep # value of map in sorted order. unmap = {} # Iterating on given array for i in range (N): # Initilize a varaible product for # calculating the product of digits product, t = 1 , arr[i] # Calculate the product of digit of # element arr[i] while (t > 0 ): product * = t % 10 t / / = 10 # Insert element into map having # product of digit in "product" temp = unmap.get(product, []) temp.append(arr[i]) temp.sort() unmap[product] = temp # Initilize a varaible result for # storing the maximum product possible result = - 1 # Iterate over the map for key, value in unmap.items(): if (key % N = = 0 and len (value) > 1 ): lastValue, secondLast = value[ - 1 ], value[ - 2 ] # Maximize the result by # product of last two # elements that are stored # in map result = max (result, lastValue * secondLast) # Return the result return result # Driver code if __name__ = = "__main__" : arr = [ 15 , 35 , 7 , 115 , 53 ] # Function Call print (maximumProduct(arr)) # This code is contributed by ragul21 |
C#
using System; using System.Collections.Generic; using System.Linq; class Program { static int MaximumProduct(List< int > arr) { int N = arr.Count; // Initialize a dictionary for mapping elements // that have the same digit product. Keep the // values in a sorted order. Dictionary< int , SortedSet< int >> dict = new Dictionary< int , SortedSet< int >>(); // Iterate over the given array foreach ( int num in arr) { int product = 1; int temp = num; // Calculate the product of the digits of the element while (temp > 0) { product *= temp % 10; temp /= 10; } // Add the element to the dictionary based on its product if (!dict.ContainsKey(product)) { dict[product] = new SortedSet< int >(); } dict[product].Add(num); } int result = -1; // Iterate over the dictionary foreach ( var pair in dict) { if (pair.Key % N == 0 && pair.Value.Count > 1) { int [] values = pair.Value.ToArray(); int maxValue = values[values.Length - 1]; int secondMaxValue = values[values.Length - 2]; result = Math.Max(result, maxValue * secondMaxValue); } } return result; } static void Main() { List< int > arr = new List< int > { 15, 35, 7, 115, 53 }; // Function Call Console.WriteLine(MaximumProduct(arr)); } } |
Javascript
// Javascript code to implement the approach // Function to find the maximum pair Product function maximumProduct(arr) { let N = arr.length; // Initilize a map for mapping elements // that have same digit product. Keep // value of map in sorted order. let unmap = new Map(); // Iterating on given array for (let i = 0; i < N; i++) { // Initilize a varaible product for // calculating the product of digits let product = 1; let t = arr[i]; // Calculate the product of digit of // element arr[i] while (t) { product *= t % 10; t = Math.floor(t / 10); } // Insert element into map having // product of digit in "product" if (!unmap.has(product)) { unmap.set(product, new Set()); } unmap.get(product).add(arr[i]); } // Initilize a varaible result for // storing the maximum product possible let result = -1; // Iterate over the map for (let [key, value] of unmap) { if (key % N === 0 && value.size > 1) { let sortedValues = Array.from(value).sort((a, b) => b - a); // Maximize the result by // product of two // elements that are stored // in map result = Math.max(result, sortedValues[0] * sortedValues[1]); } } // Return the result return result; } // Driver code let arr = [15, 35, 7, 115, 53]; // Function Call console.log(maximumProduct(arr)); |
1855
Time Complexity: O(N)
Auxiliary Space: O(N)
Contact Us