If getting TLE despite O(N)


#1

Do not store string in queue…


#2

Atleast tell what to use instead. :stuck_out_tongue:


#3

Use queue, store only integer, then backtrack to get the string…


#4

Tried both.
I pushed string in queue.
next solution I pushed long long int in queue.
both the times getting TLE.

btw, converting int to string is o(digits)
and queue also runs o(digit) times
so The solution which gives me TLE is o(digit^2) not o(N).
Correct me If I am wrong, also, let me know the correct solution approach as both passing integer or string gives me TLE.


#5

the complexity can be brouht down to O((2digits-1) + digits) this can be acheived by passing residue of modeulo with A and when res==0 generating entire string .
new_res=((prev_res
10)+char)%A;
So, basically O(2*digits-1) from qeue and additional o(digits) at final step.
But even this approach is giving TLE


#6

Hey @ShrehalB …Dont store d whole string at once as it could be very large …Dont store long long int (same reason) …dont store pairs in queue …

Use a queue to store only remainder(the states u r traversing) …
1 Take an array of integer “val” which stores only digits “0” or “1” in each cycle …so u can traverse it simply to get ur ans.
2. But as u add both 0 and 1 while traversing ur vector “val” u hv to go for only d right digits(either 0 or 1)…this u can do by having a second array “parent” which stores parent of every number …so to traverse u follow d parent chain to obtain ans from val array .
3.A flag array to mark visited d states u hv covered …so u dont cover it again and again


#7

Thansks a lot @beingayushgupta . Reached the solution. I wish you had commented earlier, would have saved some coins :joy:


#8

I’m storing the remainders in the queue. For checking whether a remainder has already been seen, I have a hash set. And for constructing the answer I have map of a remainder to a pair(parent remainder and digit that was appended to parent).

This runs in O(lengthOfTheAnswer). Still getting TLE.


#9

@ShrehalB @beingayushgupta
Could you please elaborate on the solution approach again? Still not clear.


#10

Just use remainders for a possible no. in the queue not the whole string and keep parent remainder of each remainder.