Saturday, July 30, 2022
HomeWordPress DevelopmentDepend minimal decrement prefix or suffix or increment all operations to make...

Depend minimal decrement prefix or suffix or increment all operations to make Array equal to 0


Given an array arr[] of measurement N. The duty is to make all of the array components equal to zero by making use of the minimal variety of operations. 
Following operations are allowed: 

  1. Choose an index i and reduce every aspect by 1 for the prefix as much as that index.
  2. Choose an index i and reduce every aspect by 1 for the suffix ranging from that index.
  3. Improve all the weather of the array by 1.

Examples:

Enter: arr[] = {2, 4, 6, 3, 7}
Output: Minimal operations: 12
Rationalization: Choose Index 0, and reduce all the weather from 
index 1 to 4 by 2 in 2 operations, new arr[] can be {2, 2, 4, 1, 5}.
Choose Index 1, and reduce all the weather from index 2 to 4 
by 2 in 2 operations, new arr[] can be {2, 2, 2, -1, 3}
Choose Index 3, and reduce all the weather from index 0 to 2
by 3 in 3 operations, new arr[] can be {-1, -1, -1, -1, 3}
Choose Index 3, and reduce aspect of index 4 by 4 in 4 operations,  
New arr[] can be {-1, -1, -1, -1, -1}
Improve all the weather by 1 in 1 operation,  
Remaining arr[] can be {0, 0, 0, 0, 0}
Complete, operations can be 2 + 2 + 3 + 4 + 1 = 12

Enter: arr[] = {1, 3, 5, 7, 5, 2, 8} 
Output: Minimal operations:  21 

 

Method:   

The next drawback might be solved utilizing Grasping Method

Initially make all components equal to the primary aspect after which decrement them to have worth as 0.

To do that following steps might be taken:

  • For making all the weather equal to the primary aspect, we are going to use the distinction between the consecutive components. ( arr[i+1]  – arr[i] ).  
  • If the distinction (diff = arr[i+1]  –  arr[i]) is optimistic, lower the weather of suffix ranging from index (i+1)
    • Variety of operations required = abs( diff )
  • If the distinction (diff = arr[i+1]  –  arr[i]) is detrimental, lower the weather of prefix as much as index i
    • Variety of operations required = abs( diff ) . Reducing the prefix will even lower the primary aspect of the array by abs( diff).
  • Lastly, the whole variety of required operations can be operations calculated by way of absolutely the distinction between the consecutive components of the array plus absolutely the worth of the primary aspect of the array.

Under is the implementation of the above strategy:  

C++14

  

#embody <bits/stdc++.h>

utilizing namespace std;

  

int minimumOperations(int arr[], int n)

{

    int i;

  

    

    int operations = 0;

  

    for (int i = 0; i < n - 1; i++) {

  

        

        

        

        operations += abs(arr[i + 1] - arr[i]);

  

        

        

        if (arr[i + 1] - arr[i] < 0) {

            arr[0] -= (abs(arr[i + 1] - arr[i]));

        }

    }

  

    

    

    

    operations += abs(arr[0]);

  

    

    return operations;

}

  

int principal()

{

    int arr[] = { 2, 4, 6, 3, 7 };

    int N = sizeof(arr) / sizeof(arr[0]);

  

    

    cout << "Minimal operations: "

         << minimumOperations(arr, N);

    return 0;

}

Output

Minimal operations: 12

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

RELATED ARTICLES

LEAVE A REPLY

Please enter your comment!
Please enter your name here

- Advertisment -
Google search engine

Most Popular

Recent Comments