CODEWITHSUNDEEP
pythonsortinggreedy
Gargee Suresh
Gargee Suresh

Reputation: 319

need help finding the flaw in logic to Find the minimum number of operations required to sort the array in non-decreasing order

Here's the question I'm trying to solve, https://codeforces.com/contest/1712/problem/C

You are given an array of ๐‘› positive integers ๐‘Ž1,๐‘Ž2,โ€ฆ,๐‘Ž๐‘›.

In one operation you do the following:

Choose any integer ๐‘ฅ. For all ๐‘– such that ๐‘Ž๐‘–=๐‘ฅ, do ๐‘Ž๐‘–:=0 (assign 0 to ๐‘Ž๐‘–). Find the minimum number of operations required to sort the array in non-decreasing order.

Input

Each test contains multiple test cases. The first line contains the number of test cases ๐‘ก (1โ‰ค๐‘กโ‰ค104). Description of the test cases follows.

The first line of each test case contains a single integer ๐‘› (1โ‰ค๐‘›โ‰ค105).

The second line of each test case contains ๐‘› positive integers ๐‘Ž1,๐‘Ž2,โ€ฆ,๐‘Ž๐‘› (1โ‰ค๐‘Ž๐‘–โ‰ค๐‘›).

It is guaranteed that the sum of ๐‘› over all test cases does not exceed 105.

Output

For each test case print one integer โ€” the minimum number of operations required to sort the array in non-decreasing order.

Example

inputCopy

5
3
3 3 2
4
1 3 1 3
5
4 1 5 3 2
4
2 4 1 2
1
1

outputCopy

1
2
4
3
0

Note In the first test case, you can choose ๐‘ฅ=3 for the operation, the resulting array is [0,0,2].

In the second test case, you can choose ๐‘ฅ=1 for the first operation and ๐‘ฅ=3 for the second operation, the resulting array is [0,0,0,0].

Here's my solution that fails in a hidden test case, can someone point out the flaw in logic/ missed corner case

Logic:

  1. Check if array is non-decreasing or of length 1 or number of distinct elements in array is 1, return 0
  2. Check if last element repeats, if it does return number of distinct elements in array
  3. If last element doesn't repeat, if second last element < last element recursively call function on array( first - second last element )
  4. If last element doesn't repeat, if second last element >= last element return number of distinct elements in array( first - second last element )
def distinct(arr):
    return len(set(arr))

def increase(arr):
    for i in range(len(arr)-1):
        if arr[i]>arr[i+1]:
            return False
    return True
    
def fun(arr,n):
    last_element=arr[-1]
    if (increase(arr)==True or len(arr)==1 or distinct(arr)==1):
        return 0
    elif (n-1 != (arr.index(last_element))):
        return distinct(arr)
    else:
        if arr[-2]<last_element:
            return fun(arr[:-1],n-1)
        else:
            return distinct(arr[:-1])

t=int(input())
while t>0:
    t=t-1
    n=int(input())
    arr=[int(x) for x in input().split()]
    print(fun(arr,n))

Upvotes: 0

Views: 805

Answers (1)

Tom Karzes
Tom Karzes

Reputation: 24052

Here's a case where your logic will fail:

    [5, 3, 3]

In this case, the last element repeats, so it goes to case 2 and returns the number of distinct elements, which is 2. But only one operation is needed: Replace 5 with 0 and you're done.

If the sequence ends with multiple instances of the same value, you can simply treat it as a single value. For instance, the above case is equivalent to:

    [5, 3]

which will produce 1.

Upvotes: 1

Related Questions