HomeSoftware DevelopmentDiscover the Most sum of the Array by performing the given operations

Discover the Most sum of the Array by performing the given operations


Enhance Article

Save Article

Like Article

Enhance Article

Save Article

Given an Array A[] of measurement N with repeated parts and all array parts are constructive, the duty is to search out the most sum by making use of the given operations:

  • Choose any 2 indexes and choose 2 integers(say x and y) such that the product of the weather(x and y) is the same as the product of the weather on the chosen index.
  • Ultimately, exchange the array component with x and y

Examples:

Enter: N = 3, A[] = {2, 3, 2}
Output: 14
Rationalization:

  • i = 1,  j = 2, x = 6,  y = 1 After making use of the next operation we get sum = 9(6 + 1 + 2) and array now grow to be {6, 1, 2} now we once more selected i and j and can attempt to discover i and j
  • i = 1, j = 3 array grow to be {12, 1, 1} sum grow to be 14, thus the utmost sum will stay 14 and we can not enhance additional.

Enter: N = 2, A = {1, 3}
Output: 4
Rationalization

  • i = 1, j = 2, x = 3, y = 1 After making use of the next operation we get sum = 4 array now grow to be {3, 1}. If we once more apply the operation then the array will stay the identical so the utmost sum comes out to be 4. 

Strategy: Implement the thought beneath to resolve the issue:

Discover the operations then we are able to observe that we’re multiplying 2 array parts so at every time we are going to choose one integer as product and different is 1. why? As a result of this may fulfill our situation for the operation that’s given within the query that’s product of x and y must be equal to the product of array component on the index we have now Chosen. So, we are going to comply with this operation n -1 occasions and after following the operation n -1 occasions we are going to get our remaining array which encompass n – 1 ones and one component which is the same as product of all of the array parts.

Observe the beneath steps to implement the above concept:

  • Calculate the product of the array.
  • Add n – 1 to the ultimate product of the array.
  • The ensuing variable would be the most sum attainable.

Beneath is the implementation for the above strategy:

C++

#embrace <bits/stdc++.h>

utilizing namespace std;

  

void maximumsum(int A[], int n)

{

  

    int ok = 1;

  

    

    for (int i = 0; i < n; i++) {

        ok *= A[i];

    }

  

    

    ok += n - 1;

  

    

    cout << ok << endl;

}

  

int essential()

{

  

    int n = 3;

    int A[] = { 2, 3, 2 };

  

    

    maximumsum(A, n);

  

    return 0;

}

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

RELATED ARTICLES

Most Popular

Recent Comments