0

Please note, I am not asking for code here, but I'm seeking an approach and explanation if possible.

Given an array of integers and Integer N how can we approach to find exactly four integers that will on summing up will become equal to N. There is a condition that we should find four such integers A,B,C,D which would maximize the product

AXBXCXD

Example N is 60 and array is

30,20,15,12,10,6,5,4,3,2

There are many possibilities of finding four integers, some of them are as shown below

Possibility 1

30+10+10+10=60 --> final AXBXCXD=30*10*10*10=30000

Possibility 2

15+15+15+15=60 -->final AXBXCXD=15*15*15*15=50625

The correct answer is 50625 among all possible A,B,C,D integer sets and their products and it has to be our final output.

Another example N is 8

Array is of 2 integers 4,2

Possibilities of making sum with four integers A,B,C,D is only one and it is as follows.

2+2+2+2=8 final output 2X2X2X2= 16

If array has no such possible combination of four integers to sum up to N we have to print -1 actually. That's where the array has no such possible integers.

By looking at this question I understood how recursively we can approach to solve the problem to find out subsets of array which sum up to N. But I don't understand how can we enforce the exact four integers condition from above problem statement.

halfer
  • 19,824
  • 17
  • 99
  • 186
Naseer Mohammad
  • 389
  • 4
  • 14

1 Answers1

1
  • Compute the sums of every pair and its product
  • Sort it by sum
  • For every pair that sum X, find the one that sums N - X with the highest product
  • Store the product of the 2 pairs as max between that and previous max
  • Once done, display max product

Complexity: O(n^2 * 2 log n).

juvian
  • 15,875
  • 2
  • 37
  • 38