Given an array of optimistic integer arr[] of size N and an integer Z, (Z > arr[i] for all 0 ≤ i ≤ N – 1). Every integer of the array may be transformed into the next two varieties:
- Preserve it unchanged
- Change it to Z – arr[i].
The duty is to maximise the product of the sum of those two kinds of parts.
Observe: There ought to be current at the least one ingredient of every kind.
Examples:
Enter: N = 5, arr[] = {500, 100, 400, 560, 876}, Z = 1000
Output: 290400
Clarification: arr[] = {500, 100, 400, 560, 876}
Convert parts current at indices 0, 3 and 4 to first kind = (500, 560, 876)
Convert parts current at indices 1 and a pair of to second kind
= (Z-arr[1], Z-arr[2]) = (1000 – 100, 1000 – 400) = (900, 600)
Sum of all first kind parts = 500+560+876 = 1936
Sum of all second kind parts = 900 + 600 = 1500
Product of every kind sum = 1936*1500 = 290400.
Which is most potential for this case.Enter: N = 4, arr[] = {1, 4, 6, 3}, Z = 7
Output: 100
Clarification: Change the first and final ingredient to 2nd kind, i.e.,
{7-1, 7-3} = {6, 4}. The sum is (6 + 4) = 10.
Preserve the 2nd and third ingredient as it’s. Their sum = (4 + 6) = 10 .
Product is 10*10 = 100. That is the utmost product potential.
Method: The issue may be solved utilizing Sorting based mostly on the next thought:
The thought is to kind the arr[] in reducing order, Calculate product of all potential mixtures of the categories. Get hold of most product amongst all mixtures.
Illustration:
Enter: N = 4, arr[] = {1, 4, 6, 3}, Z = 7
After sorting arr[] in reducing order = {6, 4, 3, 1}
Now now we have 3 potential mixtures for selecting all parts as first or second kind:
- 1 of first kind, 3 of second kind
- 2 of first kind, 2 of second kind
- 3 of first kind, 1 of second kind
Let’s see the product and sum at every mixture for reducing ordered arr[]:
Selecting first ingredient as first kind and subsequent 3 parts as second kind:
- Sum of first kind parts = 6
- Sum of second kind parts = ((7 – 4)+(7 – 3)+(7 – 1))= 13
- Product of first and second = 6 * 13 = 78
Selecting first two parts as first kind and final 2 parts as second kind:
- Sum of first kind parts = 6 + 4 = 10
- Sum of second kind parts = (7 – 3)+(7 – 1))= 10
- Product of first and second varieties = 10 * 10 = 100
Selecting first three parts as first kind and final ingredient as second kind:
- Sum of first kind parts = 6 + 4 + 3 = 13
- Sum of second kind parts = (7 – 1)) = 6
- Product of first and second varieties = 13 * 6 = 78
As we are able to clearly see that 2nd mixture has most worth of product.Due to this fact, output for this case is :
Most Product: 100
Comply with the steps to unravel the issue:
- Type the enter array arr[].
- Traverse from the top of the array to calculate the product for all potential mixtures:
- Think about all of the ingredient until index i as first kind, and the suffix parts as second kind.
- Calculate the product of this mix.
- Replace the utmost product accordingly.
- Print the utmost product obtained.
Beneath is the implementation of the above strategy.
Java
|
Time Complexity: O(N2)
Auxiliary House: O(1)