Max product of Array A after at most N operations, A[i]=A[i]*B[j] or A[i]=A[i]+B[j]

user_13403510 0
Viewed 146

We are given two Arrays A and B of size n with containing only positive integers. we are allowed to modify elements of array A such that A[i]=A[i]*B[j] or A[i]=A[i]+B[j], where 0<=i,j<n. we are allowed to use each element of array B only once. Find the maximum product of Array A after at most n operation. The purpose of question is to look for correct and better algorithms. example:

A={2,3,5};
B={1,6,4};
output= 1080

Explanation:

A[0]=2+1=3
A[1]=3*4=12
A[2]=5*6=30
product=30*12*3=1080

My approach:

#include <iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main() {
    int testcases; cin>>testcases;
    for(int i=0;i<testcases;i++){
        int n;cin>>n;
        vector<int>a(n);
        vector<int>b(n);
        for(int j=0;j<n;j++){
            cin>>a[j];
        }
        for(int j=0;j<n;j++){
            cin>>b[j];
        }
        sort(a.begin(),a.end());
        sort(b.begin(),b.end());
        for(int j=0;j<n;j++){
            a[j]=max(a[j]+b[j],a[j]*b[j]);
        }
        int answer=a[0];
        for(int j=1;j<n;j++){
            answer=answer*a[j];
        }
        cout<<answer<<endl;
    }
}

But, it passed only 1 testcases, and was getting wrong answer for others. kindly looking for help to approach this question.

Example of failing test cases;

A = [1,2]
B = [1,2]
My answer = 8
Correct answer = 9= [(1+2) * (1+2)]
math data-structures arrays algorithm
1 Answers

Since the numbers are positive, our only concern with addition are the 1s. All groupings that contain no 1s are optimal as multiplication, and when we multiply in that group, the ordering does not matter (since (a1 * b1) * (a2 * b2) = (a1 * b2) * (a*2 * b*1)).

The decision for 1s in both A and B is

max(2 * a * b, (a + 1) * (b + 1))
  where a and b are the next lowest non 1s

Otherwise, the leftover 1s are matched with the next lowest non-1 in the other list.

JavaScript code with testing against brute force:

function bruteForce(A, B, i = 0) {
  if (i == A.length) {
    return 1;
  }
  
  let result = 1;
  
  for (let j = 0; j < B.length; j++){
    if (B[j] != -1) {
      const copyB = B.slice();
      copyB[j] = -1;
      result = Math.max(
        result,
        A[i] * B[j] * bruteForce(A, copyB, i+1),
        (A[i] + B[j]) * bruteForce(A, copyB, i+1)
      );
    }
  }

  return result;
}

function f(A, B) {
  A.sort((a, b) => a - b);
  B.sort((a, b) => a - b);
  let i = 0;
  while (A[i] == 1) {
    i += 1;
  }
  let j = 0;
  while (B[j] == 1) {
    j += 1;
  }
  
  let result = 1;
  let ii = 0;
  let jj = 0;

  while (ii < i && jj < j && A[ii] == 1 && B[jj] == 1
    && i < A.length && j < B.length) {
    const left = 2 * A[i] * B[j];
    const right = (A[i] + 1) * (B[j] + 1);
    if (left >= right) {
      result *= 2;
    } else {
      result *= right;
      i += 1;
      j += 1;
    }
    ii += 1;
    jj += 1;
  }

  let a1count = 0;
  while (ii < A.length && A[ii] == 1) {
    a1count += 1;
    ii += 1;
  }
  
  let b1count = 0;
  while (jj < B.length && B[jj] == 1) {
    b1count += 1;
    jj += 1;
  }
  
  while (j < B.length && a1count > 0) {
    result *= B[j] + 1;
    j += 1;
    a1count -= 1;
  }

  while (i < A.length && b1count > 0) {
    result *= A[i] + 1;
    i += 1;
    b1count -= 1;
  }

  while (i < A.length && j < B.length) {
    result *= A[i] * B[j];
    i += 1;
    j += 1;
  }

  return result;
}

var numTests = 100;
var n = 5;
var m = 50;

function getArr() {
  const arr = [];
  for (let i = 0; i < n; i++) {
    arr.push(1 + Math.floor(Math.random() * m));
  }
  return arr;
}

console.log("Testing...");

for (let i = 0; i < numTests; i++) {
  const A = getArr();
  const B = getArr();
  const brute = bruteForce(A, B);
  const _f = f(A, B);
  if (brute != _f) {
    console.log("Mismatch:");
    console.log(`f: ${ _f }; brute: ${ brute }`);
    console.log(JSON.stringify(A));
    console.log(JSON.stringify(B));
  }
}

console.log("Done.");

user_20347870
Related