Friday, August 5, 2022
HomeWordPress DevelopmentMinimal operations to make Array components 0 by decrementing pair or single...

Minimal operations to make Array components 0 by decrementing pair or single aspect


View Dialogue

Enhance Article

Save Article

Like Article

Given an array arr[] of dimension N, the duty is to search out the minimal variety of operations required to cut back all three components of the array to zero. Following operations are allowed:

  • Scale back 2 totally different array components by one.
  • Scale back a single array aspect by one.

Instance:

Enter: arr[] = {1, 2, 3}, N = 3
Output: 3
Rationalization : Operation 1: cut back 3 and a pair of to get {1, 1, 2}
Operation 2: reduuce 1 and a pair of to get {1, 0, 1}
Operation 3: cut back each 1s to get {0, 0, 0}

Enter: arr[] = {5, 1, 2, 9, 8}, N = 5
Output: 13

 

Strategy:

This downside will be solved utilizing grasping method. The thought is to cut back the two largest components at a time or (if not doable) 1 at a time.  As we want the most important components in every step, we are able to use a max heap.

The next steps will be taken to resolve this method:

  • Provoke a depend variable as 0.
  • Insert all the weather in a max heap.
    • Scale back the 2 largest components.
    • Insert the diminished values once more into the heap.
  • Repeat above talked about steps till all array components grow to be zero and improve the depend at every iteration.
  • Cease when all array components are zero.

Under is the implementation of the above method:

Java

import java.util.*;

  

class GFG {

  

    public static int reduceArray(int arr[], int N)

    {

  

        int depend = 0;

        PriorityQueue<Integer> pq = new PriorityQueue<>();

  

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

            pq.add(arr[i] * -1);

        }

        whereas (pq.dimension() > 1) {

            int temp1 = pq.ballot();

            int temp2 = pq.ballot();

            depend++;

            temp1++;

            temp2++;

            if (temp1 != 0)

                pq.add(temp1);

            if (temp2 != 0)

                pq.add(temp2);

        }

        if (pq.dimension() > 0)

            depend -= pq.ballot();

        return depend;

    }

  

    

    public static void primary(String[] args)

    {

        int arr[] = { 1, 2, 3 };

        int N = 3;

        int depend = reduceArray(arr, N);

        System.out.println(depend);

    }

}

Time Complexity: O(N * logN)
Auxiliary House: O(N)

RELATED ARTICLES

LEAVE A REPLY

Please enter your comment!
Please enter your name here

- Advertisment -
Google search engine

Most Popular

Recent Comments