Thursday, August 18, 2022
HomeWordPress DevelopmentMinimal replacements with 0 to kind the array

Minimal replacements with 0 to kind the array


Given an array A[] of N integers, the duty is to search out the minimal variety of operations to kind the array in non-decreasing order, by selecting an integer X and changing all of the occurrences of X within the array with 0.

Examples:

Enter: N = 5, A[] = {2, 2, 1, 1, 3}
Output: 1
Rationalization: We select X = 2 and substitute all of the occurrences of two with 0. Now the array turns into {2, 2, 1, 1, 3} -> {0, 0, 1, 1, 3} , which is sorted in growing order.

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

 

Strategy: The issue will be solved simply with the assistance of a Map. 

Observations:

There are 2 circumstances that must be thought of :

  • Case 1: Identical aspect happens greater than as soon as non-contiguously 
    • Take into account the array : {1,6,3,4,5,3,2}. 
    • Now, since 3 at index 5 is bigger than its subsequent aspect, so we’ll make that 0 (in addition to 3 at index 2). 
    • The array turns into {1,6,0,4,5,0,2}. 
    • So, the one option to kind the array could be to make all the weather earlier than the zeroes equal to 0. i.e. the array turns into {0,0,0,0,0,0,2}.
  • Case 2: Aspect at ith index is bigger than the aspect at (i+1)th index :
    • Take into account the array : {1,2,3,5,4}. 
    • Because the aspect on the third index is bigger than the aspect at 4th index, we have now to make the aspect at third index equal to zero. 
    • So , the array turns into {1,2,3,0,4}. 
    • Now, the one option to kind the array could be to make all the weather earlier than the zero equal to 0. i.e. the array turns into {0,0,0,0,4}.

It may be noticed that ultimately Case 2 breaks right down to Case 1.

Contemplating the above circumstances, the issue will be solved following the beneath steps :

  • Declare a hash map and add the frequency of every aspect of the array into the map.
  • Iterate by means of the array from the again, i.e. from i=N-1 to i=0.
  • At every iteration, deal with Instances 1 and a pair of as defined above.
  • If iteration completes, return 0.

Under is the implementation of this strategy:

C++

#embody <bits/stdc++.h>

utilizing namespace std;

  

int minimumReplacements(int A[], int N)

{

    

    map<int, int> mp;

  

    

    

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

        mp[A[i]]++;

    }

  

    

    for (int i = N - 1; i >= 0; i--) {

  

        

        

        whereas (i > 0 && A[i] == A[i - 1]) {

            mp[A[i]]--;

            i--;

        }

  

        mp[A[i]]--;

  

        

        

        if (mp[A[i]] == 0) {

            mp.erase(A[i]);

        }

  

        

        if (mp.discover(A[i]) != mp.finish()) {

            return mp.dimension();

        }

  

        

        if (i > 0 && A[i - 1] > A[i]) {

            return mp.dimension();

        }

    }

  

    

    

    return 0;

}

  

int predominant()

{

    int N = 5;

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

  

    

    int reply = minimumReplacements(A, N);

    cout << reply;

}

Time Complexity: O(N)
Auxiliary Area: O(N) 

RELATED ARTICLES

LEAVE A REPLY

Please enter your comment!
Please enter your name here

- Advertisment -
Google search engine

Most Popular

Recent Comments