Reduce array elements

Asked by At

Given an array or list of numbers
e.g.
[1, 4, 6, 7, 9, 10, 11, 12, 13, 15]

We have to reduce the values of the array step-wise until the given number of steps. We can only reduce the array elements only if the current element is greater than the last element + 1, i.e.

if (arr[i]>arr[i-1]+1)
      arr[i] -= 1

we have to this iteration until till the required number of steps or till the array elements become continuous.

We do not reduce further if the array value has been reduced to its index.
e.g.
[1, 4, 6, 7, 9, 10, 11, 12, 13, 15]


Step-1
[1, 3, 5, 7, 8, 10, 11, 12, 13, 14]
(we did not reduce 1 since its values is same as its index, then we reduced 4 to 3 since last element is 1, 4>1+1, similarly for 6. But for 7, since the condition 7>6+1 fails so we do not reduce it.)

Step-2
[1, 2, 4, 6, 8, 10, 11, 12, 13, 14]

Step-3
[1, 2, 3, 5, 7, 9, 11, 12, 13, 14]

Step-4
[1, 2, 3, 4, 6, 8, 10, 12, 13, 14]

Step-5
[1, 2, 3, 4, 5, 7, 9, 11, 13, 14]

Step-6
[1, 2, 3, 4, 5, 6, 8, 10, 12, 14]

Step-7
[1, 2, 3, 4, 5, 6, 7, 9, 11, 13]

Step-8
[1, 2, 3, 4, 5, 6, 7, 8, 10, 12]

Step-9
[1, 2, 3, 4, 5, 6, 7, 8, 9, 11]

Step-10
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]


I am asked to return the array at K-th step. if K > step when array elements become continuous, then return the continuous. In the above example if K = 20, we will return the array of Step-10.

I wrote a python script, but it is not working for the Test Data. It is taking too much time. Can someone please provide a more optimized solution to the problem.

def reduce(arr):
    crr = []
    for i in range(1, len(arr)+1):
        if arr[i-1]!=i and arr[i-2]!=arr[i-1]-1:
            crr.append(arr[i-1]-1)
        else:
            crr.append(arr[i-1])
    return crr


brr = [int(i) for i in input().split()]
k = int(input())


goal = list(range(len(brr)))
while k!=0 and brr!=goal:
    k -= 1
    brr = reduce(brr)
print(brr)

Input:
arr = 1 4 6 7 9 10 11 12 13 15
k = 7

My Code's Output:

[1, 2, 3, 4, 5, 6, 7, 9, 11, 13]

0 Answers