# Tag Info

0

Assuming the upper bound on the maximum value of the $n$ input elements is $5n$ (as written in the question) then your solution works. Their solution works too but it is overcomplicated. If the maximum value of the $n$ input elements is at most $n^5$, then your solution would require time $\Omega(n^5)$. In general, if all $n$ input element are written in ...

2

The statement is incorrect*. Consider that $$RE = \{L(M) \mid M \text{ is a turing machine} \}$$ Thus $$\{ \langle M \rangle \mid M \text{ is a turing machine}\} \subseteq L \implies S_L =\{\ L(M) \mid \langle M \rangle \in L \} = RE$$ Therefore if I set L = \{ \langle M \rangle \mid M \text{ is a turing machine}\} \cup \{ \#\langle M \rangle \mid M \...

0

The second idea seems to guide you on the right track. You can use the fact that all multiplies of each prime cannot be co-prime. So, for 14, as an example, you can remove all multiples of 2 and seven from the list. Hence, you can remove all multiplies of 2 ($\frac{10^6}{2}$), plus all odd multiplies of 7 ($\frac{10^6}{7\times 2}$). Hence, you need to check ...

Top 50 recent answers are included