ritik652000's blog

TLE on 714B

By ritik652000, history, 4 years ago, In English

Can someone please help me, I got TLE on O(N) on 714B?

mod = 10**9 + 7
for _ in range(int(input())):
    n = int(input())
    arr = list(map(int,input().split()))
    count = arr[0]
    f = 1
    for i in range(1,n):
        count&=arr[i]
        f*=i
    f//=(n-1)
    t = arr.count(count)
    p = 1
    if(t<=1):
        print(0)
    else:
        
        p = t*(t-1)
        re = p*f
        print(re%mod)
  • Vote: I like it
  • +3
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it +5 Vote: I do not like it

I think its the 'f', you calculate f = n!, but for n = 2e5 the value is too big and the time to calculate this in python is too large. As you want the answer modulo M, you can try to calculate the answer modulo M in the for, and use modular inverse for the division.

→ Reply
»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Calculating f for a large n will be too slow. Instead you can take mod at each step. Replacing f*=i by if i<n-1: f=(f*i)%mod and removing the f//=n-1 might work.

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

For large numbers (in this case of size 1e5) even simple operations like multiplication will behave like a linear time operation. In this case, while calculating factorial of do modulo operation after each multiplication to keep the size of the number small. -> f = (f*i)%mod

→ Reply