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]](https://neveropen.co.za/wp-content/uploads/2023/10/wardslaus_quicklatex.com-a0306a0d9136f21c1d86da40032a3965_l3.png "Rendered by QuickLaTeX.com")
is called decreasing if ![arr[i] >= arr[i+1]](https://neveropen.co.za/wp-content/uploads/2023/10/wardslaus_rubhabha_quicklatex.com-e0cdf89c002c43cb87f962d6bff65415_l3.png "Rendered by QuickLaTeX.com")
for each i: 
.
Input : N = 4, K = 5, arr[] = {1, 1, 2, 3}
Output : 3Explanation :
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 =
If ( (arr[i] – arr[i-1]) % k == 0 ) then noOfSubtraction++Modify arr[i]; arr[i] =
![(arr[i] - arr[i-1]) / k](https://neveropen.co.za/wp-content/uploads/2023/10/neveropen_quicklatex.com-1f484abde718ba2b8c1eb9f7f25e0995_l3.png "Rendered by QuickLaTeX.com")
If ( (arr[i] – arr[i-1]) % k == 0 ) then noOfSubtraction++Modify arr[i]; arr[i] = ![arr[i] - ( k * noOfSubtraction )](https://neveropen.co.za/wp-content/uploads/2023/10/wardslaus_rubhabha_quicklatex.com-5a125bd4d64c6e59a4bfdeca9f687fa0_l3.png "Rendered by QuickLaTeX.com")
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 operationint 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 Codeint 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 decreasingimport 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 operationdef 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 Codearr = [ 1, 1, 2, 3 ]N = len(arr)k = 5print(min_noOf_operation(arr, N, k))# This code is contributed by# Smitha Dinesh Semwal |
C#
// C# program to make an// array decreasingusing 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 operationfunction 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> |
3
Time Complexity : O(N).
Auxiliary Space: O(1).
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
