CODEWITHSUNDEEP
arrays
Nikhil Rathore
Nikhil Rathore

Reputation: 170

Minimum increment decrement operations to make array non increasing

Given an array a, your task is to convert it into a non-increasing form such that we can either increment or decrement the array value by 1 in minimum changes possible.

Examples :

Input : a[] = {3, 1, 2, 1} Output : 1 Explanation : We can convert the array into 3 1 1 1 by changing 3rd element of array i.e. 2 into its previous integer 1 in one step hence only one step is required.

Input : a[] = {3, 1, 5, 1} Output : 4 We need to decrease 5 to 1 to make array sorted in non-increasing order.

Input : a[] = {1, 5, 5, 5} Output : 4 We need to increase 1 to 5.

This is the problem: https://www.geeksforgeeks.org/minimum-incrementdecrement-to-make-array-non-increasing/

The solution given is wrong. It is failing for this test case

{1, 2, 3, 4, 5}. The answer should be 6 with all array elements converted into 3. But the code gives 4 as the output. I don't think it is a greedy algorithm problem. What should be the approach.

Upvotes: 1

Views: 2545

Answers (1)

Prakarsh Saxena
Prakarsh Saxena

Reputation: 5

The code given in gfg is correct, you must have missed the part where they have pushed the element twice, one time inside the if and other outside the if condition P.S. I am also looking for the logic behind it.

Upvotes: 1

Related Questions