Minimum number of subtract operation to make an array decreasing

Last Updated : 28 Jul, 2022

You are given a sequence of numbers arr[0], arr[1], …, arr[N – 1] and a positive integer K. In each operation, you may subtract K from any element of the array. You are required to find the minimum number of operations to make the given array decreasing.

An array $arr[0], arr[1], ....., arr[N-1]$ is called decreasing if $arr[i] >= arr[i+1]$ for each i: $0 <= i < N-1$ .

Input : N = 4, K = 5, arr[] = {1, 1, 2, 3}
Output : 3

Explanation :

Since arr[1] == arr[0] so no subtraction is required for arr[1]. For arr[2], since arr[2] > arr[1] (2 > 1) so we have to subtract arr[2] by k and after the one subtraction value of arr[2] is -3 which is less than the value of arr[1], so number of subtraction required only 1 and now value of arr[2] has been updated by -3.
Similarly for arr[3], since arr[3] > arr[2] (3 > -3) so for this we have to subtract arr[3] by k two times to make the value of arr[3] lesser than arr[2], the number of subtraction required 2 and the updated value of arr[3] is -7. Now count total number of subtraction /operation required by adding number of operation on each step and that is = 0+1+2 = 3.

Input : N = 5, K = 2, arr[] = {5, 4, 3, 2, 1}
Output : 0

Approach :

1. Traverse each element of array from 1 to n-1.

2. Check if (arr[i] > arr[i-1]) then

Find noOfSubtraction;

noOfSubtraction = $(arr[i] - arr[i-1]) / k$ If ( (arr[i] – arr[i-1]) % k == 0 ) then noOfSubtraction++Modify arr[i]; arr[i] = $arr[i] - ( k * noOfSubtraction )$

Below is implementation of above approach :

CPP

// CPP program to make an array decreasing
#include <bits/stdc++.h>
using namespace std;
 
// Function to count minimum no of operation
int min_noOf_operation(int arr[], int n, int k)
{
    int noOfSubtraction;
    int res = 0;
    for (int i = 1; i < n; i++) {
        noOfSubtraction = 0;
 
        if (arr[i] > arr[i - 1]) {
 
            // Count how many times we have to subtract.
            noOfSubtraction = (arr[i] - arr[i - 1]) / k;
 
            // Check an additional subtraction is 
            // required or not.
            if ((arr[i] - arr[i - 1]) % k != 0)
                noOfSubtraction++;
 
            // Modify the value of arr[i].
            arr[i] = arr[i] - k * noOfSubtraction;
        }
 
        // Count total no of operation/subtraction .
        res = res + noOfSubtraction;
    }
 
    return res;
}
 
// Driver Code
int main()
{
    int arr[] = { 1, 1, 2, 3 };
    int N = sizeof(arr) / sizeof(arr[0]);
    int k = 5;
    cout << min_noOf_operation(arr, N, k) << endl;
    return 0;
}

Java

// Java program to make an
// array decreasing
import java.util.*;
import java.lang.*;
 
public class GfG{
     
    // Function to count minimum no of operation
    public static int min_noOf_operation(int arr[], 
                                      int n, int k)
    {
        int noOfSubtraction;
        int res = 0;
         
        for (int i = 1; i < n; i++) {
            noOfSubtraction = 0;
 
            if (arr[i] > arr[i - 1]) {
     
                // Count how many times 
                // we have to subtract.
                noOfSubtraction = (arr[i] - arr[i - 1]) / k;
 
                // Check an additional subtraction 
                // is required or not.
                if ((arr[i] - arr[i - 1]) % k != 0)
                    noOfSubtraction++;
 
                // Modify the value of arr[i]
                arr[i] = arr[i] - k * noOfSubtraction;
            }
 
            // Count total no of subtraction
            res = res + noOfSubtraction;
        }
 
        return res;
    }
     
    // driver function
    public static void main(String argc[]){
        int arr = { 1, 1, 2, 3 };
        int N = 4;
        int k = 5;
        System.out.println(min_noOf_operation(arr,
                                           N, k)); 
    }
     
}
 
/* This code is contributed by Sagar Shukla */

Python3

# Python program to make an array decreasing
 
# Function to count minimum no of operation
def min_noOf_operation(arr, n, k):
 
    res = 0
    for i in range(1,n):
        noOfSubtraction = 0
 
        if (arr[i] > arr[i - 1]):
 
            # Count how many times we have to subtract.
            noOfSubtraction = (arr[i] - arr[i - 1]) / k;
 
            # Check an additional subtraction is 
            # required or not.
            if ((arr[i] - arr[i - 1]) % k != 0):
                noOfSubtraction+=1
 
            # Modify the value of arr[i].
            arr[i] = arr[i] - k * noOfSubtraction
         
 
        # Count total no of operation/subtraction .
        res = res + noOfSubtraction
     
 
    return int(res)
 
 
# Driver Code
arr = [ 1, 1, 2, 3 ]
N = len(arr)
k = 5
print(min_noOf_operation(arr, N, k))
 
# This code is contributed by
# Smitha Dinesh Semwal

C#

// C# program to make an
// array decreasing
using System;
 
public class GfG{
     
    // Function to count minimum no of operation
    public static int min_noOf_operation(int []arr, 
                                       int n, int k)
    {
        int noOfSubtraction;
        int res = 0;
         
        for (int i = 1; i < n; i++) {
            noOfSubtraction = 0;
 
            if (arr[i] > arr[i - 1]) {
     
                // Count how many times 
                // we have to subtract.
                noOfSubtraction = (arr[i] - arr[i - 1]) / k;
 
                // Check an additional subtraction 
                // is required or not.
                if ((arr[i] - arr[i - 1]) % k != 0)
                    noOfSubtraction++;
 
                // Modify the value of arr[i]
                arr[i] = arr[i] - k * noOfSubtraction;
            }
 
            // Count total no of subtraction
            res = res + noOfSubtraction;
        }
 
        return res;
    }
     
    // driver function
    public static void Main()
    {
        int []arr = { 1, 1, 2, 3 };
        int N = 4;
        int k = 5;
        Console.WriteLine(min_noOf_operation(arr,
                                        N, k)); 
    }
     
}
 
// This code is contributed by vt_m 

PHP

<?php
// PHP program to make an array decreasing
 
// Function to count minimum no of operation
function min_noOf_operation($arr, $n, $k)
{
     
    $noOfSubtraction;
    $res = 0;
    for($i = 1; $i < $n; $i++) 
    {
        $noOfSubtraction = 0;
 
        if ($arr[$i] > $arr[$i - 1]) 
        {
 
            // Count how many times we
            // have to subtract.
            $noOfSubtraction = ($arr[$i] - 
                      $arr[$i - 1]) / $k;
 
            // Check an additional subtraction 
            // is required or not.
            if (($arr[$i] - $arr[$i - 1]) 
                               % $k != 0)
                $noOfSubtraction++;
 
            // Modify the value of arr[i].
            $arr[$i] = $arr[$i] - $k * 
                      $noOfSubtraction;
        }
 
        // Count total no of 
        // operation/subtraction .
        $res = $res + $noOfSubtraction;
    }
 
    return floor($res);
}
 
    // Driver Code
    $arr = array(1, 1, 2, 3);
    $N = count($arr);
    $k = 5;
    echo min_noOf_operation($arr, $N, $k) ;
 
// This code is contributed by anuj_67.
?>

Javascript

<script>
 
// JavaScript program to make an
// array decreasing
 
    // Function to count minimum no of operation
    function min_noOf_operation(arr, n, k)
    {
        let noOfSubtraction;
        let res = 0;
           
        for (let i = 1; i < n; i++)
        {
            noOfSubtraction = 0;
   
            if (arr[i] > arr[i - 1])
            {
       
                // Count how many times 
                // we have to subtract.
                noOfSubtraction = (arr[i] - arr[i - 1]) / k;
   
                // Check an additional subtraction 
                // is required or not.
                if ((arr[i] - arr[i - 1]) % k != 0)
                    noOfSubtraction++;
   
                // Modify the value of arr[i]
                arr[i] = arr[i] - k * noOfSubtraction;
            }
   
            // Count total no of subtraction
            res = res + noOfSubtraction;
        }
        return res;
    }
 
// Driver code    
        let arr = [ 1, 1, 2, 3 ];
        let N = 4;
        let k = 5;
        document.write(Math.floor(min_noOf_operation(arr,
                                           N, k)));
                                            
       // This code is contributed by code_hunt.               
</script>

Output

Time Complexity : O(N).
Auxiliary Space: O(1).

Minimize Operation to Make Array Non-decreasing or Non-increasing

Arpit_Dixit

Improve

Article Tags :

Practice Tags :

Minimum number of subtract operation to make an array decreasing

CPP

Java

Python3

C#

PHP

Javascript

Similar Reads

Thank You!

What kind of Experience do you want to share?