Let $A_1,A_2 \dots A_k $ be sets of integers such that $\left|A_{1}\right|+\left|A_{2}\right|+\dots\left|A_{k}\right|=\mathcal{O}\left(n\right) $

Find an algorithm that determines if there are $a_1+a_2+a_3+\dots a_{k-1}=a_k $ such that $a_i\in A_i $ with runtimes of $O\left(n^{\frac{k}{2}}\log\left(n\right)\right)$ for even k and $O\left(n^{\frac{k+1}{2}}\right) $ for odd k. How to find an algorithm for odd k's and even k's where k is non-constant?

So I started looking at the case of $k=2 $ and with sorting both arrays, and binary searching $a_1 $ for all $a_1\in A_1$ we can determine a solution with $$ T=\mathcal{O}\left(\overbrace{n\log\left(n\right)}^{Sort}\right)+\mathcal{O}\left(\overbrace{n}^{loop}\cdot\overbrace{\log\left(n\right)}^{B.S}\right) $$

For Even K I determined the equation can be $a_{1}+a_{2}+a_{3}+\dots a_{k-1}-a_{k}=0 $ I split the arrays into 2 sets such that $$ \overbrace{\left\{ A_{1},A_{2},A_{3}\dots A_{\frac{k}{2}}\right\} }^{Q},\overbrace{\left\{ A_{\frac{k}{2}+1},A_{\frac{k}{2}+2}\dots-A_{k}\right\} }^{P} $$

at most each $A_i $ has $n $ elements so the number of sums possible is $n^\frac{k}{2}$ for $P$ and the same is true for $Q$. Afterwards I can use sort and binary search, just as in $k=2$, but the runtime for sorting is $\mathcal{O}\left(n^{\frac{k}{2}}\log\left(n^{\frac{k}{2}}\right)\right)=\mathcal{O}\left(kn^{\frac{k}{2}}\log\left(n\right)\right) $ and for non constant-k it does not work.

For odd k I don't have an idea, since looking at the runtime no sorting is needed, it seems like a completely different problem.



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Browse other questions tagged or ask your own question.