Given an array of constructive 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 varieties of components.

Be aware: There ought to be current not less than one factor 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 components current at indices 0, 3 and 4 to first kind =  (500, 560, 876)
Convert components current at indices 1 and a couple of to second kind 
= (Z-arr[1],  Z-arr[2]) = (1000 – 100, 1000 – 400) = (900, 600)
Sum of all first kind components = 500+560+876 = 1936
Sum of all second kind components = 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 factor to 2nd kind, i.e.,
{7-1, 7-3} = {6, 4}. The sum is (6 + 4) = 10.
Preserve the 2nd and third factor as it’s. Their sum = (4 + 6) = 10 .
Product is 10*10 = 100. That is the utmost product potential.

Strategy: The issue may be solved utilizing Sorting primarily based on the next concept:

The concept is to type the arr[] in reducing order, Calculate product of all potential mixtures of the kinds. Receive 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 components 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 factor as first kind and subsequent 3 components as second kind:

  • Sum of first kind components = 6
  • Sum of second kind components = ((7 – 4)+(7 – 3)+(7 – 1))= 13
  • Product of first and second = 6 * 13 = 78

Selecting first two components as first kind and final 2 components as second kind:

  • Sum of first kind components = 6 + 4 = 10
  • Sum of second kind components = (7 – 3)+(7 – 1))= 10
  • Product of first and second varieties = 10 * 10 = 100

Selecting first three components as first kind and final factor as second kind:

  • Sum of first kind components = 6 + 4 + 3 = 13
  • Sum of second kind components = (7 – 1)) = 6
  • Product of first and second varieties = 13 * 6 = 78

As we will clearly see that 2nd mixture has most worth of product.Due to this fact, output for this case is : 

Most Product: 100

Observe 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 factor until index i as first kind, and the suffix components as second kind.
    • Calculate the product of this mix.
    • Replace the utmost product accordingly.
  • Print the utmost product obtained.

Under is the implementation of the above strategy.

Java

  

import java.util.*;

  

class GFG {

  

    

    public static void predominant(String[] args)

    {

        lengthy[] arr = { 500, 100, 400, 560, 876 };

        int N = arr.size;

        lengthy Z = 1000;

  

        

        System.out.println(Max_Product(N, arr, Z));

    }

  

    

    

    static lengthy Max_Product(int n, lengthy[] arr, lengthy Z)

    {

        

        lengthy product = Lengthy.MIN_VALUE;

  

        

        Arrays.type(arr);

  

        

        lengthy sum1 = 0;

  

        

        

        lengthy X = Integer.MIN_VALUE;

  

        

        

        lengthy Y = Integer.MAX_VALUE;

  

        

        

        for (int i = n - 1; i > 0; i--) {

            sum1 += arr[i];

            lengthy sum2 = 0;

            for (int j = i - 1; j >= 0; j--) {

                sum2 = sum2 + (Z - arr[j]);

            }

            if (sum1 * sum2 > product) {

                product = sum1 * sum2;

                X = sum1;

                Y = sum2;

            }

        }

  

        return (product);

    }

}

Time Complexity: O(N2)
Auxiliary House: O(1)

By admin

Leave a Reply

Your email address will not be published.