For each non beautiful tree at position A[i], if there is a tree at A[i] + 2, plant a tree at A[i] + 1, else plant a tree at A[i] - 1.
Why does my approach fail?
For each non beautiful tree at position A[i], if there is a tree at A[i] + 2, plant a tree at A[i] + 1, else plant a tree at A[i] - 1.
Why does my approach fail?
1
5
1 2 5 8 11
gives WA for this.
answer should be 3 not 2.
Trees should be planted at 6 9 and 10 right? (one solution)
Please correct me if I am wrong, but planting a tree at position 2 and 7 would suffice in this case right?
oh wait…yes you are right.
Lemme check there’s a similar test case to this then
will edit it
@sapient Everything is fine but you just need to sort the array.
Check out this test case with your solution and compare with sorted arr (just use sort(arr, arr+n)
) solution:
1
5
9 2 6 1 4
Here is my explained editorial
Happy coding
What is wrong with this code?
t = int(input())
for _ in range(t):
n = int(input())
a = list(map(int, input().split(' ')))
a.sort()
a.insert(0, a[0] - 4)
a.append(a[-1] + 4)
s = set(a)
count = 0
for i in range(1,n+1):
if a[i]+1 not in s and a[i]-1 not in s:
count += 1
s.add(a[i]+1)
#print('**', a)
#print('**', s)
print(count)
It’s getting runtime error…
Thank you, I’ve realised my mistake
Problem with your program is, it is not working for unsorted array or for the arrays which are reversed sorted.
Example: 11 9 7 5 3 1
Actual Output: 3
Your code’s output: 5