New answers tagged counting
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
