Make an increasing array, while modifying the array

Question

Q: You are given an array of n integers. You want to modify the array so that it is increasing, i.e., every element is at least as large as the previous element.

On each move, you may increase the value of any element by one. What is the minimum number of moves required?

Input:

5

3 2 5 1 7

Output: 5

My attempt at the solution:

input number of elements in list
input elements of list as string, and convert to a list of integers
make a function that stores the number of moves as the difference of non-increasing elements. ex: in list [1,2,4,3], 4 is greater than 3, so it is non increasing, so I find the difference between the terms, and add it to the number of moves.
add the difference to the lesser term (i.e make list [1,2,4,3] into [1,2,4,4])
call this function whenever i'th term is lesser than (i+1)'th list of list
Print the total number of moves

My code:

a = input('')
b = list(map(int, a.split(' ')))    # split string into a list of numbers
sum1 = 0
def moves(i):
    global sum1
    for i in range(len(b)-1):
        if b[i] < b[i+1]:
            sum1 += b[i] - b[i+1]
            b[i + 1] += b[i] - b[i+1]
        else:
            moves(i+1)
print(sum1)
moves(0)

What is wrong in the implementation and how can I correct it?

@user202729, it just returns 0 for everything (after changing sum to sum1) — Dudeness
– Dudeness, Commented Feb 20, 2021 at 5:59

Tim Roberts · Accepted Answer · 2021-02-20 06:35:29Z

1

Recursion is totally the wrong way to do this. All you need is one pass through the list. And don't use globals; just return the final result. Note that you had your comparison backwards. You want cases where b[i] > b[i+1], not <.

a = input('')
b = list(map(int, a.split()))

def moves(b):
    sum1 = 0
    for i in range(len(b)-1):
        if b[i] > b[i+1]:
            sum1 += b[i] - b[i+1]
            b[i+1] = b[i]
    return sum1

print(moves(b))

answered Feb 20, 2021 at 6:35

Tim Roberts

55.3k4 gold badges28 silver badges41 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Dirk Herrmann · Accepted Answer · 2021-02-20 09:01:21Z

What is wrong in the implementation and how can I correct it?

In your function you don't print anything. You print sum1, however, before you call moves(0), but at that time the value of sum1 is still 0.
You are mixing recursion and iteration: The for loop by itself already covers the whole list and (with some corrections) is already close to solving the problem iteratively. Still you make an additional recursive call. Since you have tagged the question "recursion" I assume you would like to understand how a recursive solution could look in principle.
Your attempt at recursion will fail because moves(i) gets an argument i but you don't use that argument value and immediately overwrite i in the for i loop. Therefore, every recursive call will again iterate over the full list.
The comparison b[i] < b[i+1] is wrong, because whenever b[i] <= b[i+1] there is nothing to do between these two list elements (assuming that all elements up to b[i] already form a non-decreasing sequence). That is, a working recursive approach could look like follows:

a = input('')
b = list(map(int, a.split(' ')))    # split string into a list of numbers
sum1 = 0
def moves(i):
    global sum1
    if i < len(b)-1:
        if b[i] > b[i+1]:
            sum1 += b[i] - b[i+1]
            b[i+1] += b[i] - b[i+1]
        moves(i+1)
moves(0)
print(sum1)

This code works, but has some non-functional quality issues:

Use of globals should be avoided. There are good reasons for this - I recommend a bit of research to understand why, rather than just accepting it as a dogma. You can transform their use into the use of function arguments and return values.
There is some unnecessary duplication of computations: b[i] - b[i+1] is computed twice. Such redundancy is disadvantageous (search for code duplication to learn why). You could use a temporary variable here to compute the value only once, but there is an even simpler approach: Do a bit of math to figure out what b[i+1] += b[i] - b[i+1] will result in.

Thanks, a lot. I honestly just typed whatever came to mind at that point of time. Next time, i'll be more careful.

bui · Accepted Answer · 2021-11-28 07:21:37Z

0

n=int(input())
lst=list(map(int,input().split()))
iter=0
count=0
for i in range(n-1):
    iter=lst[i]
    ahead=lst[i+1]
    diff=iter-ahead
    if(diff>0):
        count+=diff
        lst[i+1]=iter
print(count)

answered Nov 28, 2021 at 7:21

bui

1

Collectives™ on Stack Overflow

Make an increasing array, while modifying the array

3 Answers 3

Comments

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related