gokulraaj59's blog

By gokulraaj59, history, 6 weeks ago, In English

1466B - Last minute enhancements i have tried to solve this with a time complexity of O(n) even with Fast_IO too it gave me an TLE //python code

for t in range(0, int(input())):
    n = int(input())
    ar = list(map(int, input().split()))
    ar.sort()
    
    op = [ar[0]]
    
    for i in ar[1:]:
        op.sort()
        if op[-1] == i:
            op.append(i+1)
        else:
            op.append(i)
        
    # print(ar)
    # print(op)
    print(len(set(op)))
    # print()

my solution 168486304

can I have a better solution ???

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by gokulraaj59 (previous revision, new revision, compare).

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

The size of your $$$op$$$ array increases by one each iteration. So sorting it once has time complexity $$$O(N \cdot \log(N))$$$. Doing this each iteration is the reason for TLE.