|
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++
#include <bits/stdc++.h>
using namespace std;
int maximumProduct(vector<int>& arr)
{
int N = arr.size();
unordered_map<int, multiset<int> > unmap;
for (int i = 0; i < N; i++) {
int product = 1, t = arr[i];
while (t) {
product *= t % 10;
t /= 10;
}
unmap[product].insert(arr[i]);
}
int result = -1;
for (auto it : unmap) {
if (it.first % N == 0 && it.second.size() > 1) {
auto i = it.second.rbegin();
result = max(result, *i * *(++i));
}
}
return result;
}
int main()
{
vector<int> arr = {15, 35, 7, 115, 53};
cout << maximumProduct(arr);
return 0;
}
|
Java
import java.util.*;
class GFG {
static int maximumProduct(int[] arr)
{
int N = arr.length;
Map<Integer, List<Integer> > unmap
= new HashMap<>();
for (int i = 0; i < N; i++) {
int product = 1, t = arr[i];
while (t > 0) {
product *= t % 10;
t /= 10;
}
List<Integer> temp = unmap.getOrDefault(
product, new ArrayList<>());
temp.add(arr[i]);
unmap.put(product, temp);
}
int result = -1;
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);
result = Math.max(result,
lastValue * secondLast);
}
}
return result;
}
public static void main(String[] args)
{
int[] arr = { 15, 35, 7, 115, 53 };
System.out.println(maximumProduct(arr));
}
}
|
Python3
def maximumProduct(arr):
N = len(arr)
unmap = {}
for i in range(N):
product, t = 1, arr[i]
while (t > 0):
product *= t % 10
t //= 10
temp = unmap.get(product, [])
temp.append(arr[i])
temp.sort()
unmap[product] = temp
result = -1
for key, value in unmap.items():
if (key % N == 0 and len(value) > 1):
lastValue, secondLast = value[-1], value[-2]
result = max(result, lastValue * secondLast)
return result
if __name__ == "__main__":
arr = [15, 35, 7, 115, 53]
print(maximumProduct(arr))
|
C#
using System;
using System.Collections.Generic;
using System.Linq;
class Program
{
static int MaximumProduct(List<int> arr)
{
int N = arr.Count;
Dictionary<int, SortedSet<int>> dict = new Dictionary<int, SortedSet<int>>();
foreach (int num in arr)
{
int product = 1;
int temp = num;
while (temp > 0)
{
product *= temp % 10;
temp /= 10;
}
if (!dict.ContainsKey(product))
{
dict[product] = new SortedSet<int>();
}
dict[product].Add(num);
}
int result = -1;
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 };
Console.WriteLine(MaximumProduct(arr));
}
}
|
Javascript
function maximumProduct(arr) {
let N = arr.length;
let unmap = new Map();
for (let i = 0; i < N; i++) {
let product = 1;
let t = arr[i];
while (t) {
product *= t % 10;
t = Math.floor(t / 10);
}
if (!unmap.has(product)) {
unmap.set(product, new Set());
}
unmap.get(product).add(arr[i]);
}
let result = -1;
for (let [key, value] of unmap) {
if (key % N === 0 && value.size > 1) {
let sortedValues = Array.from(value).sort((a, b) => b - a);
result = Math.max(result, sortedValues[0] * sortedValues[1]);
}
}
return result;
}
let arr = [15, 35, 7, 115, 53];
console.log(maximumProduct(arr));
|
Time Complexity: O(N)
Auxiliary Space: O(N)
|
