Tuesday, March 2, 2021

Published March 02, 2021 by Anonymous with 0 comment

Minimize replacements with values up to K to make sum of two given arrays equal

import java.util.*;

  

class GFG {

  

    

    

    

    public static int makeSumEqual(

        int[] a, int[] b, int K,

        int M, int N)

    {

        

        int sum1 = 0;

  

        

        int sum2 = 0;

  

        

        for (int el : a)

            sum1 += el;

  

        

        for (int el : b)

            sum2 += el;

  

        

        

        int diff = sum1 - sum2;

  

        

        

        int l1 = 0, r1 = M - 1;

  

        

        

        int l2 = 0, r2 = N - 1;

  

        

        int res = 0;

  

        

        

        Arrays.sort(a);

        Arrays.sort(b);

  

        

        

        while (l1 <= r1 || l2 <= r2) {

            if (diff == 0) {

  

                break;

            }

  

            

            if (diff > 0) {

  

                

                if (l2 <= r2 && l1 <= r1) {

  

                    if (K - b[l2] < a[r1] - 1) {

  

                        int sub = Math.min(

                            a[r1] - 1, diff);

                        diff -= sub;

                        a[r1] -= sub;

                        r1--;

                    }

                    else {

  

                        int sub = Math.min(

                            K - b[l2], diff);

                        diff -= sub;

                        b[l2] += sub;

                        l2++;

                    }

                }

  

                

                

                else if (l1 <= r1) {

  

                    int sub = Math.min(

                        a[r1] - 1, diff);

                    diff -= sub;

                    a[r1] -= sub;

                    r1--;

                }

  

                

                else {

  

                    int sub = Math.min(

                        K - b[l2], diff);

                    diff -= sub;

                    b[l2] += sub;

                    l2++;

                }

            }

  

            

            else {

  

                

                if (l1 <= r1 && l2 <= r2) {

                    if (K - a[l1]

                        < b[r2] - 1) {

  

                        int sub = Math.min(

                            b[r2] - 1,

                            -1 * diff);

                        diff += sub;

                        b[r2] -= sub;

                        r2--;

                    }

  

                    else {

  

                        int sub = Math.min(

                            K - a[l1],

                            -1 * diff);

                        diff += sub;

                        a[l1] -= sub;

                        l1++;

                    }

                }

  

                

                

                else if (l2 <= r2) {

  

                    int sub

                        = Math.min(

                            b[r2] - 1,

                            -1 * diff);

                    diff += sub;

                    b[r2] -= sub;

                    r2--;

                }

  

                

                else {

  

                    int sub = Math.min(

                        K - a[l1], diff);

                    diff += sub;

                    a[l1] += sub;

                    l1++;

                }

            }

  

            

            

            res++;

        }

  

        

        if (diff == 0)

            return res;

  

        

        else

            return -1;

    }

  

    

    public static void main(String[] args)

    {

        int[] A = { 1, 4, 3 };

        int[] B = { 6, 6, 6 };

        int M = A.length;

        int N = B.length;

        int K = 6;

  

        System.out.println(

            makeSumEqual(A, B, K,

                         M, N));

    }

}

Let's block ads! (Why?)

      edit

0 comments:

Post a Comment