bitwise operation

bitwise

#1

i dont understand why 1 one is faster than 2 :-


##1:-

for j in array:
 number+=(1<<(k-j))

##2:-

for j in array:
 number+=(1<<(j))

link to the problem here

first solution link here


second solution link here


#2

@phantomhive the first difference is that the first one is compiled in PyPy and the other in Python. However even when both are compiled on PyPy or Python there is significant difference (> 3s) between the execution times. I tried a few variations to understand what’s going on but sadly I don’t.

If anyone else can figure it out, please do, this is very curious :smiley:


#3

i think it about the input.. the input data must have more big number which when done this "number+=1«number" and when we or it larer takes much time as the number is too large but when we do this "1«(k-number)" where "k>=number" we make sure that we set bit from right not from left that results in a small number but it only works if we have more big numbers and less small numbers!


#4

Yes that might be it. I tried to test this locally using Python, and for the worst case of T=10, N=K=2500, and each set={K}, the solutions took 9.39 and 11.7 seconds. But clearly if the test data had such a case neither solution would pass at all (assuming my system is at least as fast as the judge). So I reduced the difficulty of test cases and got something like 4.49 and 5.79 seconds which is close to the result on submission. So you’re probably right.