FastPrep
Problem · Array

Maximize Capped Contribution Sum

Learn this problem
● EasyVisa logoVisaFULLTIMENEW GRADOA

Problem statement

You are given two integer arrays a and b of the same length and an integer k. For each index i, that index contributes min(a[i], b[i]) to a total sum.

You may choose at most k distinct indices. For each chosen index, replace b[i] with 2 * b[i]. After applying those changes, the contribution of that index becomes min(a[i], 2 * b[i]).

Return the maximum possible total contribution.

Function

maximizeCappedContributionSum(a: int[], b: int[], k: int) → long

Complete the function maximizeCappedContributionSum in the editor below.

maximizeCappedContributionSum has the following parameters:

  1. int[] a: the first array
  2. int[] b: the second array
  3. int k: the maximum number of indices whose b[i] value can be doubled

Returns

long: the maximum possible total sum.

Examples

Example 1

a = [5, 8, 4]b = [3, 6, 10]k = 1return = 15

The initial contribution is min(5,3) + min(8,6) + min(4,10) = 3 + 6 + 4 = 13. If you double b[0], the first contribution becomes min(5,6) = 5. If you double b[1], the second becomes min(8,12) = 8. Either choice gives a gain of 2, so the best total is 15.

Example 2

a = [10, 7, 6, 4]b = [2, 5, 4, 3]k = 2return = 18

The initial total is 2 + 5 + 4 + 3 = 14. Doubling index 0 changes its contribution to min(10,4)=4, a gain of 2. Doubling index 1 changes its contribution to min(7,10)=7, a gain of 2. Doubling index 2 changes its contribution to min(6,8)=6, a gain of 2. Any two of those three gains produce the maximum total 14 + 2 + 2 = 18.

Constraints

The source thread did not provide explicit numeric bounds.

  • a.length == b.length
  • 0 <= k <= a.length
  • Each index may be doubled at most once.

More Visa problems

drafts saved locally
public long maximizeCappedContributionSum(int[] a, int[] b, int k) {
    // write your code here
}
a[5, 8, 4]
b[3, 6, 10]
k1
expected15
checking account