Tuesday, September 20, 2022
HomeWordPress DevelopmentMaximize the Product of Sum by changing Array parts into given two...

Maximize the Product of Sum by changing Array parts into given two varieties


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

  

import java.util.*;

  

class GFG {

  

    

    public static void important(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.kind(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)

RELATED ARTICLES

LEAVE A REPLY

Please enter your comment!
Please enter your name here

- Advertisment -
Google search engine

Most Popular

Recent Comments